Minimum Travel Cost

In this problem, you are given a complete undirected weighted graph representing a network of n cities and the travel costs between them. Your task is to determine the minimum travel cost to start from city 0, visit every city exactly once, and return to the starting city. This is the classical Travelling Salesman Problem (TSP).

The cost of the tour is given by

$$\text{Cost} = c_{0,P(1)} + c_{P(1),P(2)} + \cdots + c_{P(n-1),0} $$

where (P) is a permutation of ({1, 2, \dots, n-1}) representing the order in which the cities are visited. All cost values are non-negative integers and the matrix is symmetric, i.e. (c_{ij} = c_{ji}).

The input starts with an integer t, the number of test cases. For each test case, the first integer is n (the number of cities), followed by an n×n matrix of travel costs. Your solution should compute the minimum travel cost for each test case and print each result on a separate line.

inputFormat

The input is given via standard input (stdin). The first line contains an integer t (1 ≤ t ≤ 100), the number of test cases. For each test case, the first line contains an integer n (2 ≤ n ≤ 15), the number of cities. This is followed by n lines, each containing n space-separated integers representing the travel cost matrix. The j-th integer in the i-th line represents the cost to travel from city i to city j. It is guaranteed that the diagonal elements are zero and the matrix is symmetric.

outputFormat

For each test case, print the minimum travel cost on a new line to standard output (stdout).## sample

2
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
3
0 29 20
29 0 15
20 15 0

80
64

</p>