Our salesman residing in Bangalore city is planning to visit a bunch of cities in India and then return back to Bangalore, all by airplanes. He needs your help in minimizing the total airfare.

Input

The input begins with the number t of test cases in a single line (t<=10). Each test case begins with number n of number of cities (excluding Bangalore) to be visited (n<=10) and (n+1)*(n+1)-(n+1) lines having airfare between each pair of cities (INR 0 <= airfare <= INR 10000). The order of airfares are as follows. Airfares from Bangalore to all other cities are listed first in some order of the cities (city 1, city 2, ..., city n), followed airfares from city 1 to Bangalore, city 2, city 3, ..., city n and so on. The adjacency matrix for the graph in the first example input below would be:
0         2000    6000    7000
3000    0         8000    3000
5000    9000    0         1000
8000    4000    1000    0

Output

For every test case print the minimum total cost of the airfares to for a tour from Bangalore to all other cities and back to Bangalore.

Example

Input:
2
3
2000
6000
7000
3000
8000
3000
5000
9000
1000
8000
4000
1000
2
1000
5000
5000
1000
1000
5000

Output:
11000
3000