#include <cstdio>

using namespace std;
int c[1000005], a[8][1000005];
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int N,K,T;
    int i,j,ok;

    for(i=0 ; i<=1000000 ; i++)
        a[0][i]=1;
    for(i=1 ; i<=7 ; i++)
        a[i][0]=0;
    N=1000000;
    //Generam ciurul
    for(i=2 ; i<=N ; i+=2)
        c[i]=1;
    for(i=3 ; i<=N ; i+=2)
        if( !c[i] )
            for(j=i ; j<=N ; j+=i)
                c[j]++;
    //Generam matricea
    for(i=0 ; i<=7 ; i++)
        for(j=1 ; j<=N ; j++)
            if(c[j]==i)
                a[i][j]=j;
            else
                a[i][j]=a[i][j-1];

    scanf("%d", &T);
    while(T)
    {
        ok=1;
        scanf("%d%d", &N, &K);
        T--;
        printf("%d", a[K][N]);
        printf("\n");
    }

    return 0;
}