/*
  [NWERC'06] BOOKCASE
  by: Jan Kuipers
*/

using namespace std;

#include <iostream>
#include <vector>
#include <algorithm>

const int infty = 99999;

int main () {

  int runs;
  cin>>runs;
  
  while (runs--) {
    int N;
    cin>>N;
    vector<pair<int,int> > b(N);
    for (int i=0; i<N; i++)
      cin>>b[i].first>>b[i].second;
    sort(b.begin(),b.end(),greater<pair<int,int> >());
    
    vector<int> h(N),t(N),tsum(N+1);
    for (int i=0; i<N; i++) {
      h[i]=b[i].first;
      t[i]=b[i].second;
      tsum[i+1]=tsum[i]+t[i];
    }

    vector<vector<int> > H(tsum[N]+1, vector<int>(tsum[N]+1, infty));
    H[0][0]=0;
    
    for (int i=0; i<N; i++)
      for (int T1=tsum[i+1]; T1>=0; T1--)
	for (int T2=tsum[i+1]; T2>=0; T2--) {
	  if (T1> t[i]) H[T1][T2] <?= H[T1-t[i]][T2];
	  if (T1==t[i]) H[T1][T2] <?= H[T1-t[i]][T2] + h[i];
	  if (T2> t[i]) H[T1][T2] <?= H[T1][T2-t[i]];
	  if (T2==t[i]) H[T1][T2] <?= H[T1][T2-t[i]] + h[i];
	}

    int res = INT_MAX;
    for (int T1=1; T1<=tsum[N]; T1++)
      for (int T2=1; T2<=tsum[N]; T2++)
	res <?= (T1 >? T2 >? (tsum[N]-T1-T2)) * (h[0]+H[T1][T2]);
    cout << res << endl;
  }

  return 0;
}