Gozz is still trying to build the best haunted house in town. He has a new plan to optimise the spookiness. He already has \(N\) rooms, but hasn't yet built the hallways between the rooms. All the hallways Gozz can build are undirected, and so can be traversed in either direction. Each hallway goes from some room to a different room--there are no hallways that lead from a room to itself. Every hallway has an associated comfort value, which is how comfortable people feel traversing that hallway. Comfort values can be negative, which indicates that the hallway causes anxiety.

Since building hallways costs Gozz money, he will always build the minimum number of hallways such that it is possible to reach any room from any other via a sequence of hallways. Subject to this constraint, Gozz wants to minimise the sum of comfort values for all the hallways he builds. We shall call any set of hallways that meet these first two constraints a valid hallway plan. Finally, Gozz has found people tend to hide in dead ends, and avoid his spooky hallways. A dead end is a room with only a single connecting hallway. Among all valid hallway plans, what is the smallest number of dead ends possible?

Input Specification

The first line contains an integer \(T\), the number of test cases to follow. Each test case will begin with a line containing a single integer, \(N\), the number of rooms for that test case. Each test case will then have \(N\) lines that follow, each containing \(N\) integers, which define a matrix, \(A\). The \(c\)th integer on the \(r\)th line will correspond to \(A_{r,c}\), the comfort level of the hallway between rooms \(r\) and \(c\). Note that the value of \(A_{r,c}\) will always be the same as \(A_{c,r}\) as hallways are undirected. Also, the value of \(A_{i,i}\) for any \(i\) should be ignored, since no hallway can be built between a room and itself. Also, note that \(A_{r, c}=0\) indicates a valid hallway with comfort level zero.

Output Specification

For each each test case, output a single line containing a single integer. The minimum number of dead ends possible over all valid hallway plans.

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 20 points: \(2 \leq N \leq 3\)
• 150 points: \(2 \leq N \leq 11\)

For all sub-problems:

\(1 \leq T \leq 10\)

\(-1000 \leq A_{r,c} \leq 1000\)

Sample Input

3
2
0 1
1 0
4
0 1 -1 1
1 0 -1 1
-1 -1 0 1
1 1 1 0
4
0 -1 -1 -1
-1 0 5 5
-1 5 0 5
-1 5 5 0

Sample Output

2
2
3