#include<cstdio>
#define N 1000001
int p[N],x[N],l,i,j,n,r[N],s[N][8],t,k,a;
int main()
{freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
x[++l]=2;
for(i=1;((i*i)<<1)+(i<<1)<N;i++)      
if((p[i>>3]&(1<<(i&7)))==0) 
      for(j=((i*i)<<1)+(i<<1);(j<<1)+1<N;j+=(i<<1)+1) 
            p[j>>3]|=(1<<(j&7));
for(i=1;2*i+1<N;i++) 
if((p[i>>3]&(1<<(i&7)))==0)
      x[++l]=2*i+1;
for(i=1;i<=l;i++)
for(j=x[i];j<N;j+=x[i])
      r[j]++;
for(i=1;i<N;i++)
      {for(j=0;j<8;j++)
             s[i][j]=s[i-1][j];
      s[i][r[i]]=i;}
scanf("%d",&t);
while(t--)
      scanf("%d%d",&n,&k),printf("%d\n",s[n][k]);
return 0;}