PESADA04 - Travelling Salesman Problem

no tags 

Our saleman 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. Aurfares 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 adjacecy matrix for th 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 airpfares 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


Added by:Prof. Channa Bankapur
Date:2015-01-27
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C