#include <cstdio>
#include <algorithm>

using namespace std;

int c[1000005],mat[1000005][8];

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int i,j,t,n,k;
    c[2]=1;
    for (i=2;i<=1000000;i=i+2)
         c[i]++;
    for (i=3;i<=1000000;i=i+2)
         if (c[i]==0)
         {
         c[i]=1;
         for (j=2*i;j<=1000000;j=j+i)
              c[j]++;
         }
    for(i=2;i<=1000000;i++)
        for(j=1;j<=7;j++)
            if(c[i]==j)
                mat[i][j]=i;
            else
                mat[i][j]=mat[i-1][j];
    scanf("%d",&t);
    for (i=1;i<=t;i++)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",mat[n][k]);
    }
    return 0;
}