// Arup Guha
// 8/18/2026
// Solution to DP Traveling Salesman Practice Problem: Visiting Relatives

import java.util.*;

public class relatives_memo {

	public static int n;
	public static double[][] dp;
	public static double[][] cost;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
		
			// Set up arrays.
			n = stdin.nextInt();
			dp = new double[n][1<<n];
			for (int j=0; j<n; j++)
				Arrays.fill(dp[j], -1);
				
			cost = new double[n][n];
			
			// Get costs.
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					cost[i][j] = stdin.nextDouble();
					
			// Will get over-written.
			double res = 1000000;
			
			// Try each location as the first one.
			for (int i=1; i<n; i++) 
				res = Math.min(res, cost[0][i]+go(i, 1<<i));
				
			// Ta da!
			System.out.printf("%.2f\n", res);
		}
	}
	
	public static double go(int at, int mask) {
	
		// Done, no more cost.
		if (mask == ( (1<<n)-1 ) ) return 0;
		
		// We did this.
		if (dp[at][mask] > -.5) return dp[at][mask];
		
		// This is enough.
		double res = 1000000;
		
		// Try all possible next locations.
		boolean left = false;
		for (int i=1; i<n; i++) {
		
			// Been at i before.
			if ((mask & (1<<i)) != 0) continue;
			
			// Add cost of this edge to the recursive cost of the rest.
			res = Math.min(res, go(i, mask | (1<<i) ) + cost[at][i] );
			left = true;
		}
		
		// We updated our result so return it.
		if (left) return dp[at][mask] = res;
		
		// We can go home!
		return dp[at][mask] = cost[at][0];
	}
}