#include <cstdio>
FILE *f=fopen ("divprim.in","r");
FILE *g=fopen ("divprim.out","w");

using namespace std;

int main()
{
    long t,k,y,d,ok=0,nr=0,x,divizori,i,j,n;
    fscanf (f,"%ld",&t);
    for (j=1;j<=t;j++)
       {
           fscanf(f,"%ld%ld",&n,&divizori);
           x=n;
    do{
        nr=0;
        i=2;
    while (x>1){
        if (x%i==0)
        {
            k=0;
            nr++;
            while (x%i==0)
            {
            k=k+1;
            x=x/i;
           }

    }
    i=i+1;
    }
     if (nr!=divizori)
     x=x-1;
    }while (nr!=divizori);
    fprintf (g,"%ld",x);


       }
    return 0;
}