#include <cstdio>
#define nmax 1000001
#define nmax1 10000

using namespace std;

bool ciur[nmax];
int num[nmax1];
inline bool fct(int numar, int nr, int x)
{
    int j=1;
    while(numar&&j<=nr)
    {
        if(numar%num[j]==0)
        {
            x--;
            j++;
            numar/=num[j];
        }else if(numar>num[j])
        {
            j++;
        }else if(numar<num[j])
        {
            break;
        }
    }
    if(x==0)
        return 1;
    else
        return 0;
}
inline int cautbin(int mini, int maxi, int k, int nr)
{
    int maaax=-1;
    int med=mini+(maxi-mini)/2;
    while(mini<=maxi)
    {
        if(fct(med, nr, k)==true)
        {
            if(maaax<med)
                maaax=med;
        }
        mini=med+1;
        med=mini+(maxi-mini)/2;
    }
    return maaax;
}
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    int n, t;
    short k;

    ciur[0]=ciur[1]=1;
    for(int i=4;i<=nmax;i+=2)
        ciur[i]=1;
    int nr=0;
    num[++nr]=2;
    for(int i=3;i*i<=nmax;i++)
    {
        if(ciur[i]==0)
        {
            num[++nr]=i;
            for(int j=i*i;j<=nmax;j+=2*i)
                ciur[j]=1;
        }
    }

    scanf("%d", &t);
    while(t)
    {
        scanf("%d%hd", &n, &k);
        int limm=1;
        int ck=k;
        int f=1;
        while(ck)
        {
            limm*=num[f];
            f++;
            ck--;
        }
        if(limm>n)
        {
            printf("0\n");
            t--;
            continue;
        }else if(limm==n)
        {
            printf("%d\n", n);
            t--;
            continue;
        }
        int maxim=limm;
        int maax=cautbin(maxim, n, k, nr);
        if(maax>maxim)
            printf("%d\n", maax);
        else
            printf("%d\n", maxim);
        t--;
    }

    return 0;
}