#include <stdio.h>
#include <string.h>
#define nmax 1000001

int k,nr[nmax];
long n,i,j,t,b[nmax][7];

void memorizare()
{
for (i=2;i*2<nmax;++i)
     nr[2*i]=1;
nr[2]=1;
for (i=3;i<nmax;i+=2)
     if (nr[i]==0)
         {
         nr[i]=1;
         for (j=2;j*i<nmax;++j)
             ++nr[j*i];
         }
for (i=2;i<nmax;++i)
    {
    memcpy(b[i],b[i-1],sizeof(b[i-1]));
    if (nr[i]<8) b[i][nr[i]-1]=i;
    }
}

int main()
{
 memorizare();
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 scanf("%ld\n",&t);
 for (i=0;i<t;++i)
     {
     scanf("%ld %d\n",&n,&k);
     if (k==0) printf("%d\n",1);
     else printf("%ld\n",b[n][--k]);
     }
fclose(stdin);
fclose(stdout);
return 0;
}