ADAPARTI - Ada and Parties

no tags 

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.

Harsh warning: I'm verry sorry but I don't (currently) have tester, so the only one who tested the correctness was me myself (so there is big percentage of problem being wrong). In this case I apologise (this warning will be withdrawn as soon as Blue.Mary will get AC :P ).

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 Ai,j (either 0 or 1), where 1 means the ith friend likes jth (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


Added by:morass
Date:2017-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All