#include <cstdio>
const int nmax=1000000;
int cdp[nmax+1];
int sol[8][nmax+1];
using namespace std;

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