#include<cstdio>
#define MAXIM 1000000
int ciur[MAXIM+1];
int v[8][MAXIM+1];
int main()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 int t;
 scanf("%d ",&t);
 int in=2,sf=1000;
 while(in<=sf)
       {
        ciur[in]=1;
        for(int j=2;j*in<=sf;j++)
            ciur[j*in]++;
        do
         {
          in++;
         }
        while(in<=sf && ciur[in]!=0);
       }
 for(int i=0;i<=7;i++)
     for(int j=1;j<=MAXIM;j++)
         {
          if(ciur[j]==i)
             v[i][j]=j;
          else
             v[i][j]=v[i][j-1];
         }
 for(int q=1;q<=t;q++)
     {
      int n,k;
      scanf("%d %d ",&n,&k);
      printf("%d\n",v[k][n]);
     }
fclose(stdin);
fclose(stdout);
return 0;
}