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 non-negative 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² + ... + 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 space-separated 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⁹

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 zero-matrix, for a zero matrx, we will never be able to make P + P² + ... + 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.