#include<stdio.h>
#include<string.h>
long a[1000005],b[100005][10];
long i,j,k,l,x,s,sp,t,valid,zero=0;
main()
{
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(a[i+k]<=100000);
     }
   i++;
   }while(i<=50000);

for(i=1;i<=10;i++)
 {b[1][i]=0;b[2][i]=0;}
b[2][1]=2;
i=3;
do{
   for(j=1;j<=7;j++)
    b[i][j]=b[i-1][j];
   b[i][ a[i]]=i;
   i++;
   }while(i<=1000);

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







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