/*********************************
* The Bookcase
* Author: A. Björklund
**********************************/
#include <stdio.h>

#define max(a,b) ((a)>(b)?(a):(b))
#define MAXN (100)
#define MAXW (50*MAXN)
struct tbook {int h,t;};
int m,n;
short mx[MAXW][MAXW][2];
struct tbook book[MAXN];
int csum[MAXN];

int cmp(void* a,void *b)
{
  return ((struct tbook*)b)->h-((struct tbook*)a)->h;  
}

int main()
{
  int i,j,k,sum,best;
  scanf("%d",&m);
  while (m--)
  {
    scanf("%d",&n);  
    for (i=0;i<n;i++)
      scanf("%d %d",&book[i].h,&book[i].t);  
    qsort(book,n,sizeof(struct tbook),cmp);  
    csum[0]=book[0].t;
    for (i=1;i<n;i++)
      csum[i]=csum[i-1]+book[i].t;
  
    for (i=0;i<csum[n-1];i++)
      for (j=0;j<csum[n-1];j++)
        mx[i][j][0]=mx[i][j][1]=MAXW;
    
    for (i=1;i<n;i++)
      for (j=csum[i-1];j>=0;j--)
        for (k=csum[i-1]-j;k>=0;k--)
          if (mx[j][k][0]<MAXW || mx[j][k][1]<MAXW || (!k && j==csum[i-1]))
          {
            if (mx[j][k][0]+mx[j][k][1]<mx[j+book[i].t][k][0]+mx[j+book[i].t][k][1])
            {
              mx[j+book[i].t][k][0]=mx[j][k][0]; // Book on first level
              mx[j+book[i].t][k][1]=mx[j][k][1]; 
            }
            if (mx[j][k][1]+(mx[j][k][0]==MAXW?book[i].h:mx[j][k][0])<
                mx[j][k+book[i].t][0]+mx[j][k+book[i].t][1])
            {
              mx[j][k+book[i].t][0]=(mx[j][k][0]==MAXW?book[i].h:mx[j][k][0]); // Book on second level 
              mx[j][k+book[i].t][1]=mx[j][k][1]; 
            }
            if (mx[j][k][1]==MAXW) mx[j][k][1]=book[i].h; // Book on third level 
          }
    
    best=1e9;
    for (j=csum[n-1];j>=0;j--)
      for (k=csum[n-1]-j;k>=0;k--)
        if (csum[n-1]-j-k>0)
        {
          int h=mx[j][k][0]+mx[j][k][1]+book[0].h;
          int w=max(csum[n-1]-j-k,max(j,k));
          if (w*h<best) best=w*h;
        }
    printf("%d\n",best);     
  }
}