## PESADA04 - Travelling Salesman Problem

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

5000Output: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 |