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