#include<stdio.h>
#include<string.h>
long a[1000005],b[1000005][55];
main()
{
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<=1000000);
     }
   i++;
   }while(i<=500000);

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

fscanf(stdin,"%ld",&t);
s=50;
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;
}