#include<stdio.h>
#include<string.h>
main()
{
int a[400005],b[400005][8];

long i,j,k,n,m,l,x,s,sp,t,valid,zero=0;
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);

memset(a,0,sizeof(a));
a[0]=1;a[1]=1;
i=2;
do{
   if(a[i]==0)
     { k=0;
       do{
	   a[i+k]++;
	   k+=i;
	  }while((k+i)<=100000);
     }
   i++;
   }while(i<=50000);

for(i=1;i<=7;i++)
 {b[1][i]=0;b[2][i]=0;}
b[2][1]=2;
n=1;i=3;
do{
   for(j=1;j<=7;j++)
    b[i][j]=b[i-1][j];
   b[i][ a[i]]=i;
   if(a[i]>n)n=a[i];
   i++;
   }while(i<=100000);

fscanf(stdin,"%ld",&t);
for(i=1;i<=t;i++)
 { fscanf(stdin,"%ld%ld",&k,&l);
   if(b[k][l]>50)fprintf(stdout,"%ld\n",zero);
   else fprintf(stdout,"%ld\n",b[k][l]);
 }







fclose(stdin);
fclose(stdout);
return 0;
}