///Pasca Robert
/// C.n.i. "Grigore Moisil"
/// a X-a
/// [email protected]

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int rezolvare(int x,int div)
{
    int e=0,d=2;
    while(x!=1)
    {
        if(x%d==0)
        {
            e++;
            while(x%d==0)
                x/=d;
        }
        d++;
    }
    if(e==div)
        return 1;
    return 0;
}
int main()
{
    int t,ok;
    f>>t;
    long long a[2][t];
    for(int i=0; i<t; i++)
        f>>a[1][i]>>a[2][i];

    for(int i=0; i<t; i++)
    {
        if(rezolvare(a[1][i],a[2][i])==1)
            g<<a[1][i]<<endl;
        else
        {
            a[1][i]--;
        }
    }
    return 0;
}