Minimum Travel Cost

You are given a number of cities and the travel cost between every pair of cities. Your task is to find the minimum travel cost to visit every city exactly once and return to the starting city (city 1). This is a classic Traveling Salesman Problem (TSP) that can be solved using dynamic programming with bit masking.

In this problem, you will be provided multiple test cases. For each test case, the first input is an integer N (the number of cities), followed by N lines each containing N integers representing the cost matrix. The travel cost from the i^th city to the j^th city is given by the element at row i and column j in this matrix.

The problem can be mathematically formulated as:

$$ \min_{\pi \in S_{N-1}} \{ c_{1,\pi(1)} + c_{\pi(1),\pi(2)} + \cdots + c_{\pi(N-1),1} \} $$

where \( c_{i,j} \) represents the travel cost from city \( i \) to city \( j \), and \( S_{N-1} \) is the set of permutations of cities \(2,3,...,N\).

inputFormat

The input is given via stdin and has the following format:

T
N
row1
row2
... 
rowN
[repeat the above block T times]

Where:

• T is the number of test cases.
• For each test case, N (an integer) represents the number of cities.
• Then follow N lines, each containing N space-separated integers representing the cost matrix.

outputFormat

For each test case, output a single line (to stdout) containing one integer: the minimum travel cost to visit all cities and return to the starting city.

## sample

1
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80