Traveling Salesman Problem

You are given a complete graph with N cities and the distances between every pair of cities. Your task is to determine the minimum cost of a tour that starts at a city, visits every other city exactly once, and returns to the starting city.

This problem is the classic Traveling Salesman Problem (TSP). Given a distance matrix D where the element \(D_{ij}\) represents the distance from city \(i\) to city \(j\), you must compute the minimum tour length. The brute force solution involves checking all possible permutations, which is feasible for small values of \(N\).

inputFormat

The first line contains an integer T — the number of test cases.

For each test case, the first line contains an integer N — the number of cities. It is followed by N lines, each containing N space-separated integers; the \(j\)-th integer in the \(i\)-th line denotes \(D_{ij}\), the distance from city \(i\) to city \(j\).

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum tour cost.

Output is written to standard output (stdout).

## sample

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

80

</p>