// Arup Guha
// 3/28/2017
// Solution to Wall Street Monopoly, written in class (uses memoization)

import java.util.*;

public class wallst_memo {

	final public static int MULT = 100;

	// Store input and answers to recursive calls.
	public static int n;
	public static int[][] dim;
	public static int[][] memo;

	// Pre-computed sub-dimensions. subDim[i][j] will store length and depth
	// of buildings i through j.
	public static int[][][] subDim;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process all cases.
		for (int loop=1; loop<=numCases; loop++) {

			// Read in the dimensions.
			n = stdin.nextInt();
			dim = new int[n][2];
			for (int i=0; i<n; i++) {
				dim[i][0] = stdin.nextInt();
				dim[i][1] = stdin.nextInt();
			}

			// Set up memo table.
			memo = new int[n][n];
			for (int i=0; i<n; i++) Arrays.fill(memo[i], -1);

			// Pre-calculate dimensions of every possible building fuse.
			subDim = new int[n][n][2];
			for (int i=0; i<n; i++) {
				subDim[i][i][0] = dim[i][0];
				subDim[i][i][1] = dim[i][1];
				for (int j=i+1; j<n; j++) {
					subDim[i][j][0] = subDim[i][j-1][0] + dim[j][0];
					subDim[i][j][1] = Math.max(subDim[i][j-1][1], dim[j][1]);
				}
			}

			// Output result.
			System.out.println("The minimum cost for lot #"+loop+" is $"+solve(0, n-1)+".");
			System.out.println();
		}
	}

	// Returns best cost of fusing building[start..end]
	public static int solve(int start, int end) {

		// Standard base cases in a memo solution.
		if (start == end) return 0;
		if (memo[start][end] != -1) return memo[start][end];

		// Set this high enough.
		int res = 1000000000;

		// Try each split/fuse point.
		for (int split = start; split<end; split++) {
			
			// Recursive costs on both ends.
			int leftCost = solve(start, split);
			int rightCost = solve(split+1, end);
			
			// Get teh appropriate dimensions for oru const function.
			int minLeft = Math.min(subDim[start][split][0], subDim[start][split][1]);
			int minRight = Math.min(subDim[split+1][end][0], subDim[split+1][end][1]);
			
			// Calculate cost for this split and update our best seen, if necessary.
			res = Math.min(res, leftCost+rightCost+MULT*minLeft*minRight);
		}

		// Store and return.
		return memo[start][end] = res;
	}
}