#include <cstdio>

using namespace std;

int v[1000010],sol[1000010][8];
int i,j,x,t,n,k;

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