#include <bits/stdc++.h>

using namespace std;

int const nMax = 20;

int n, k[nMax], c[nMax];

int answer;
int steps;

void fun (const int position, const int orc1, const int orc2, const int orc3, const int current) {
	steps++;
	if (current > answer) {
		return;//useless branch
	}
	if (position == n) {
		answer = min(answer, current);
		return;//final state
	}
	//fight
	if (orc1 + orc2 + orc3 >= k[position]) {
        int n1 = orc1, n2 = orc2, n3 = orc3;
		int enemy = k[position];
		int toFight = min(enemy, n3);
		n3 -= toFight;
		enemy -= toFight;
		toFight = min(enemy, n2);
		n2 -= toFight;
		enemy -= toFight;
		toFight = min(enemy, n1);
		n1 -= toFight;
		enemy -= toFight;
		fun(position + 1, 0, n1, n2, current);
	}
	//pay
	fun(position + 1, orc1, orc2, orc3, current + c[position]);
	//hire
	fun(position + 1, orc1 + k[position], orc2, orc3, current + c[position] + c[position]);
}

const bool DEBUG = true;

int main () {
	int tests;
	cin >> tests;
	for (int t = 1; t <= tests; t++) {
        steps = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> k[i] >> c[i];
		}
		answer = 100000000;
        auto s = clock();
		fun(0, 0, 0, 0, 0);
		cout << "#" << t << " " << answer;
        if (DEBUG) {
            cout << " steps = " << steps;
            cout << " time = " << fixed << setprecision(3) << (clock() - s) * 1.0 / CLOCKS_PER_SEC;
        }
        cout << endl;
	}
	
	return 0;
}