#include <cstdio>
#define NMAX 1000000
using namespace std;
char prim[NMAX];
int P[NMAX],nr=0;
void ciuruiala(){
    int i,j;
    P[0]=2;
    prim[1]=0;
    for (i=3;i<=NMAX;i+=2)
    prim[i]=1;
    for (i=3;i<=NMAX;i+=2){
    if (prim[i]){
            P[++nr]=i;
            for (j=i+i+i;j<=NMAX;j+=i<<1){
                    prim[j]=0;}
    }
    }
}
   int solve (int N, int nr){
        int i,nr2=0;
    for (i=0;i<=500000&&1LL*P[i]*P[i]<=N;i++){
        if (N%P[i])
            continue;
        nr2++;
while (N%P[i]==0)
{N/=P[i];}
    }
    if (N>1&&P[i]*P[i]>N)
        nr2++;
return nr2;}
int main()
{freopen ("divprim.in", "r", stdin);
freopen ("divprim.out", "w", stdout);
int n,i;
int x,y,sol;
scanf ("%d", &n);
ciuruiala();
for (i=1;i<=n;i++){
        scanf ("%d %d", &x, &y);
if (solve(x,y)==y)
    printf ("%d", x);
else{
        while (solve(x,y)!=y&&x>0){
                x--;}
printf ("%d", x);}
printf ("%c", '\n');
}
return 0;
}