Minimal Travel Time

You are given several test cases, each representing a variant of the Traveling Salesman Problem (TSP). In each test case, you are provided with:

• An integer N representing the number of stations.
• A cost matrix C of dimensions N × N, where the element \(C_{i,j}\) denotes the travel time (or cost) from station i to station j.
• An integer S (1-indexed) indicating the starting station.

Your task is to determine the minimal travel time required to start at station \(S\), visit every other station exactly once, and then return to station \(S\). The cost of a route defined by a permutation \(\pi\) (of all stations except \(S\)) is given by:

\(C_{S, \pi(1)} + \sum_{i=1}^{N-2} C_{\pi(i), \pi(i+1)} + C_{\pi(N-1), S}\)

Output the minimal route cost for each test case on a new line.

inputFormat

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

T
N
C[0][0] C[0][1] ... C[0][N-1]
C[1][0] C[1][1] ... C[1][N-1]
...
C[N-1][0] C[N-1][1] ... C[N-1][N-1]
S
(repeat the above block T times)

Where:

• T is the number of test cases.
• For each test case, the first integer N denotes the number of stations.
• The next N lines each contain N space-separated integers representing the cost matrix.
• The last line of each test case contains S, the starting station index (1-indexed).

outputFormat

For each test case, output a single line containing a single integer which is the minimal travel time required to visit all stations and return to the starting station.

The results should be printed to standard output (stdout) in the same order as the corresponding test cases in the input.

## sample

2
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
1
3
0 5 6
5 0 7
6 7 0
2

80
18

</p>