Iguana

In the park of flora and fauna, a major redevelopment project is underway. The organizers have planned to expand the park's area, increase the number of exotic animals, and construct new enclosures. Once the plan received approval, builders and zoologists began their work.

The zoologists successfully completed their task by bringing in new giraffes, long-awaited elephants, iguanas from the Caribbean islands, and many other animals and birds. However, the builders were unable to finish the new enclosures in time, so it was decided to temporarily house the animals in cages.

This task presented its own challenges, as there might not be enough cages for all the animals. Additionally, only compatible animals can share the same cage. To address this, the zoologists created a compatibility table for the animals, represented as a matrix (A = {a_ij}) of size (N×N). If animals numbered (i) and (j) are compatible, then (a_ij = 0); if they are not, then (a_ij = 1). The goal is to determine the minimum number of cages required to safely house the animals, ensuring that each cage contains only mutually compatible animals. A cage can hold one or more animals.

Input

The first line of the input file contains a single number (T) – the number of test cases. Following this, there are (T) test descriptions. Each test begins with a line containing the number (N) – the number of animals ((0 < N $\le$ 100)). This is followed by (N) lines, each containing (N) numbers that form the animal compatibility matrix.

Output

For each test case, output a single integer on a separate line – the minimum number of cages required for the safe placement of the animals.

Examples