Ada the Ladybug is already planning her birthday party. It is not an easy process since she has many friends. At first, she had a plan to invite only subset of her friends but now her plans are different. She wants to satisfy all her friends so she is going to hold multiple parties. Anyway she wants to satisfy fact, that each of her friends will have all of their friends at the same party while there will be no one, who is not his/her friend.

Problem is, that with current layout, it might not be possible. It is not so easy to let two bugs become friend, and it is not so "nice" to make them enemies... yet both are possible. Ada asked you to find the minimal number of such operations so that the parties will be possible! Ada doesn't want to do many of such operations so she already made a little research and found out she won't need more than 12 such operations.

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 ≤ 62, 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)

Note, that the matrix will be symmetrical.

Each insect is friend with itself!

Output

For each test-case output the minimal number of introductions and antagonizations.

Example Input

7
7
1 0 0 0 0 0 0
0 1 1 1 0 0 0
0 1 1 0 0 0 1
0 1 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 1 0 0 0 1
8
1 1 1 0 0 0 1 1
1 1 1 0 0 0 0 1
1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
8
1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 1 0 0 0 0 0 1
3
1 0 0
0 1 0
0 0 1
7
1 1 0 0 0 1 0
1 1 0 0 1 0 1
0 0 1 1 0 0 1
0 0 1 1 0 0 0
0 1 0 0 1 0 0
1 0 0 0 0 1 1
0 1 1 0 0 1 1
6
1 1 1 0 0 0
1 1 1 0 1 1
1 1 1 0 0 0
0 0 0 1 0 0
0 1 0 0 1 1
0 1 0 0 1 1
5
1 1 1 1 1
1 1 1 1 0
1 1 1 0 1
1 1 0 1 1
1 0 1 1 1

Example Output

2
4
1
0
4
2
2