No Unpaired Chefs

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Codechef has now decided to make an admin panel amongst their chefs. This way they think that it would be easier for them to control and regulate their contests. To do so, they have asked them to rate everyone including themselves by a nonnegative integer.
There are N chefs, numbered from 1 to N. Each chef has submitted a rating to the Codechef panel for other all the chefs including a rating to himself. Surprisingly for the team, for each pair of chefs (say, chef with the number i and the chef with the number j), they collaborated within themselves and gave the same rating to each other i.e. the rating that the chef i has given to the chef j is equal to the rating that the chef j has given to the chef i. The Codechef team built a rating matrix from this input from Chefs. Now, from this input rating matrix M, they will make a Paired rating matrix P as follows:
 P is symmetric.
 P_{i, j} is either equal to zero, or to M_{i, j}, where M_{i, j} is the rating given by i^{th} chef to the j^{th} chef.
 There exists S > 0, such that each entry in P + P^{2} + ... + P^{S} is positive.
 To make things more friendly between the admin panel of Chefs, the sum of values in P is minimum possible.
Help the Codechef panel in selecting such a matrix P from M. Please find the minimum possible sum of entries in the matrix P such that P will still satisfy the constraints.
Input
The first line of the input contains T, number of test cases to follow. Then T test cases follow.
Each test case start with a line containing an integer N, the number of chefs in Codechef team.
Then N lines follow. Each of them contains N spaceseparated integers. The j^{th} integer in the i^{th} line is the rating given by chef with the number i to chef with the number j.
Output
For each test case, print the minimum sum of entries, possible for P. If it is not possible to do, print "1" (without quotes).
Constraints
 1 ≤ T ≤ 100
 Constraints on N:
 Subproblem 1 (30 points): 1 ≤ N ≤ 5
 Subproblem 2 (70 points): 1 ≤ N ≤ 100
 0 ≤ M_{i, j} ≤ 10^{9}
Example
Input: 2 2 1 0 0 1 2 1 1 1 1 Output: 1 2
Explanation:
In the first sample case, there are only two choices of choosing P, one is a zeromatrix, for a zero matrx, we will never be able to make P + P^{2} + ... + P^{S} all positive. Another choice is to chose P = M, for this case also, we can never make the sum with all positive values for any S.
In the second case, if one selects P such that we eliminate diagonal elements from M, we get all sum positive for S=2 itself. One can check that this is the minimum sum value for P possible to satisfy all constraints.
Author:  pnkjjindal 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/UNPAIR 
Tags  graphtheory, ltime22, mediumhard, mst, pnkjjindal 
Date Added:  14032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 