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