Christopher's Key Ring

Time Limit: 2 Seconds    Memory Limit: 32768 KB

As you've known in "Christopher's Christmas Letter" problem, Christopher has been out of danger. But soon he found that he lost a key ring in the hospital, which was a precious Christmas gift from his lover. Certainly Christopher does NOT want to lose it, lose the past beatific state of mind. Don't you have the heart to help him?

Naturally, he won't ask you to find it physically, coz he could hire a child labor for physical help. But involved problem he met is that he should give exact amount of money to the child labor, neither more nor less than the money needed. (I'm sorry to tell you that he has spent too much money in hospital, and must be economical now). For a single unit length's examination, Christopher should pay 1 dollar.

The ichnograph of hospital is a TREE in graph theory, i.e. there's exactly one path between every pair of nodes. Sickrooms in the hospital are all leaf nodes. Corridors connecting them might intersect at some guarding rooms (they are considered as particles). How to count the total length of corridors? Christopher ALWAYS counts the same unit of length again and again, so he calls you for help.

Sadly, the only information that could be gained from the principal of hospital is the distance between every pair of sickrooms.

Input

The first line of input contains a number X which denotes the number of test cases. For each test case:

Line 1: n (2 <= n <= 777) Number of the rooms in the hospital

Line 2~n+1: The number in (i+1)th row and jth column denotes the distance between sickroom i and sick room j (not more than . We ensure the number in (i+1)th row and ith column is always ZERO, and the number in (i+1)th row and jth column is always SAME as the number in (j+1)th row and ith column.

There're NO breakline between two continuous test cases.

Output

Exact X lines, each one contains the number money (in dollars) should be paid. We guarantee that the answer won't be larger than 10^9.

Sample Input

2
3
0 6 5
6 0 7
5 7 0
3
0 6 5
6 0 7
5 7 0

Sample Output

9
9

Submit

Source: Online Contest of Christopher's Adventure