#include<stdio.h>
#include<math.h>
long long int n,t,a,d,i,j,prim[1003];
int ok,k;
long int prim1000()  //primele 1000 nr prime
{
     prim[1]=2; i=1;
     for(a=3;i<=1000;a+=2)
     {  ok=1;
        for(d=2;d<sqrt(a);d++)
            if(a%d==0){ok=0; break;}
        if(ok) prim[++i]=a;
     }
     return 0;
}
int main()
{   prim1000();
    FILE *f=fopen("divprim.in","r");
    FILE *g=fopen("divprim.out","w");
    fscanf(f,"%lld",&t);
    for(j=1;j<=t;j++)
    { fscanf(f,"%lld%d",&n,&k);
      ok=0;
      for(a=n;ok==0;a--)
      { d=0;
        for(i=1;i<=1000&&a!=1;i++) { if(a%prim[i]==0)
                                        { d++; while(a%prim[i]==0) a/=prim[i];}
                                     if(d==k) break;
                                    }
        if(a==1) ok=1;
        }
       fprintf(g,"%lld",a);
      }
    fcloseall();
    return 0;
}