#include<cstdio>
#define NMAX 1300000
using namespace std;
char prim[NMAX];
int P[NMAX/2+1],K=0;
void ciur(){
    prim[1]=0,prim[2]=1;
    P[0]=2;
    int i,j;
    for (i=3;i<=NMAX;i+=2)
        prim[i]=1;
    for (i=3;i<=NMAX;i+=2){
            if (prim[i]){
                    P[++K]=i;
            for (j=i+i+i;j<=NMAX;j+=i<<1){
                    prim[j]=0;
            }
            }
    }
}
void sol(int x, int nr){
    int s=0,i=0,ok1=0,p=1;
while (P[i]<x){
    i++;}
for (;i>=0&&!ok1;i--){
        if (1LL*P[i]*P[i]<=x){
    p*=P[i];
s++;
if (s==nr){
        ok1=1;}
        if (nr==1)
            p*=p;}
}
if (s==nr&&p<=x){
        printf ("%d", p);
}
else {
        printf ("%d", 0);}
printf ("%c", '\n');
}

int main(){
    freopen ("divprim.in", "r", stdin);
    freopen ("divprim.out", "w", stdout);
    int n,i,x,nr;
    scanf ("%d", &n);
    ciur();
    for (i=1;i<=n;i++){
            scanf ("%d %d", &x, &nr);
            sol(x,nr);}
            return 0;
            }