Byteotia is a country consisting of $n$ cities (numbered from 1 to $n$) and bidirectional highways connecting them. Traveling along a highway between two cities requires burning one bajtoliter of fuel. Balthazar, the CEO of BajtTrans, is very unhappy with the fuel consumption, so he plans to place a bidirectional teleport between two certain cities in Byteotia. A trip by teleport is instantaneous and consumes no fuel! The trucks of BajtTrans must have a fuel tank large enough to be able to travel between any pair of cities in Byteotia on a single tank of fuel filled at the starting city (fuel consumed within each city is not taken into account, as it is negligibly small).

Balthazar would like to minimize the size of the fuel tank in the trucks. Given the description of the Byteotian highways, determine the minimum required tank size, assuming that the pair of cities connected by the teleport is chosen optimally. You may assume that it is possible to travel between any pair of cities using the highways. You must solve this problem for $t$ independent test cases.

Input

The first line of the input contains the number $t$ ($1 \le t \le 21$), representing the number of test cases.

The first line of the description of each test case contains the number $n$ ($3 \le n \le 400$), representing the number of cities in Byteotia. The next $n$ lines of the test case contain the description of the highways in Byteotia. Each of them contains a binary string of length $n$. The $i$-th element in the $j$-th string is equal to 1 if and only if there is a highway connecting cities numbered $i$ and $j$.

Each highway connects two different cities – the $i$-th element in the $i$-th string is always 0. Each highway is bidirectional – the $i$-th element in the $j$-th string is equal to the $j$-th element in the $i$-th string. Using the described highways, it is possible to travel between any pair of cities in Byteotia.

The sum of $n$ over all test cases will not exceed 400.

Output

The output should contain $t$ lines, with the $i$-th line containing a single integer representing the minimum fuel tank size of the truck (in bajtoliters) with an optimal teleport placement for the $i$-th test case.

Examples

Input 1

2
4
0111
1011
1101
1110
5
01000
10100
01010
00101
00010

Output 1

1
2

Note

In the first test case, it is possible to travel directly by highway between any pair of cities, and regardless of which cities we connect with a teleport, we will still need a tank with a capacity of at least 1 bajtoliter.

In the second test case, before setting up the teleport, with a tank capacity of two bajtoliters, it is not possible to travel between cities numbered (1, 4), (1, 5), and (2, 5). However, after setting up the teleport (for example, between cities numbered 1 and 5), it becomes possible.