Ada the Ladybug is already planning her birthday party. It is not an easy process since she have many friends but each of her friends likes just about half of her other friends. She wants to invite only such subset of friends that everyone likes each other.

Ada has barely some time and she wants big party so she asked you to find maximum such list in which each of her friends is friend with each of her other friends on the list.

Input

The first line contains an integer 1 ≤ T ≤ 100, the number of test-cases.

The first line of each test-case begins with 1 ≤ N ≤ 130, the number of her friends.

Each of next N lines contain N integers A_i,j (either 0 or 1), where 1 means the i^th friend likes j^th (and 0 means the opposite)

Important note is, that as brain connections of insect are not so complicated as those of humans, so the process of making friends is slightly different. Two insects have exactly 50% chance of being friends, so also the adjancecy matrix will be generated (very)pseudo-randomly with 50% chance for each edge.

Also note, that the matrix will be symmetrical.

Each insect is friend with itself!

Output

For each test-case output the maximum number of Ada's friends, which can be invited.

Example Input

10
7
1 1 0 0 1 1 0
1 1 1 0 1 1 0
0 1 1 0 1 0 1
0 0 0 1 0 0 1
1 1 1 0 1 1 0
1 1 0 0 1 1 0
0 0 1 1 0 0 1
5
1 1 1 1 0
1 1 1 0 1
1 1 1 1 0
1 0 1 1 0
0 1 0 0 1
1
1
4
1 0 0 1
0 1 0 1
0 0 1 0
1 1 0 1
1
1
10
1 1 0 1 0 1 0 1 1 1
1 1 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 0 1 0
1 1 0 1 1 1 1 0 1 0
0 0 0 1 1 0 0 0 1 1
1 0 0 1 0 1 0 1 0 0
0 1 0 1 0 0 1 0 1 1
1 0 0 0 0 1 0 1 1 1
1 0 1 1 1 0 1 1 1 0
1 0 0 0 1 0 1 1 0 1
7
1 1 0 1 1 0 0
1 1 1 0 1 0 0
0 1 1 0 0 1 0
1 0 0 1 1 0 0
1 1 0 1 1 0 1
0 0 1 0 0 1 0
0 0 0 0 1 0 1
3
1 1 0
1 1 1
0 1 1
8
1 0 1 1 1 1 0 0
0 1 0 1 1 1 1 1
1 0 1 1 0 1 0 1
1 1 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 1
0 1 0 1 0 1 1 1
0 1 1 1 1 1 1 1
6
1 0 1 0 0 1
0 1 0 0 0 1
1 0 1 1 1 0
0 0 1 1 0 1
0 0 1 0 1 0
1 1 0 1 0 1

Example Output

4
3
1
2
1
3
3
2
4
2