Traveling Salesman Problem

You are given a complete weighted directed graph with n cities. The cost of travelling from city i to city j is provided in an n × n cost matrix. Your task is to find the minimum cost path that starts at city 0, visits every other city exactly once, and returns to city 0.

This is a classic NP-hard problem known as the Traveling Salesman Problem (TSP).

The recurrence for the dynamic programming solution is given by:

$$dp[pos][mask] = \min_{\text{city not in } mask} \{ \text{cost}(pos,city) + dp[city][mask \cup \{city\}] \} $$

where mask is a bitmask representing the set of visited cities, and the base case occurs when all cities have been visited:

$$dp[pos][mask] = \text{cost}(pos,0) \quad \text{if} \quad mask = 2^n - 1. $$

inputFormat

The input is read from stdin and has the following format:

T
n
c[0][0] c[0][1] ... c[0][n-1]
...
c[n-1][0] c[n-1][1] ... c[n-1][n-1]

Here, T is the number of test cases. For each test case, the first line contains the integer n (the number of cities). The next n lines each contain n integers, representing the cost matrix.

outputFormat

For each test case, output the minimum cost for completing the tour (visiting all cities exactly once and returning to the starting city) on a new line to stdout.

## sample

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

80

</p>