///Rozmarin Andrei
///CNI "Grigore Moisil"
///a X-a B
///[email protected]



#include <fstream>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

int n,a[100000],x,nr;

int nr_div(int &y)
{
    int nrdiv=0,x=y;
    if(x%2==0 && x>0)
        nrdiv++;

    while(x%2==0)
        x/=2;

    for(int d=3;d<=x;d+=2)
    {
        if(x%d==0)
            nrdiv++;
        while(x%d==0)
            x/=d;
    }

    return nrdiv;
}

int prop(int &x,int &nrdivizori)
{
    for(int i=x;i>1;i--)
    {
        if(nr_div(i)==nrdivizori)
        {
            return i;
        }
    }
    return 0;
}



int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x>>nr;

        a[i]=prop(x,nr);
    }

    for(int i=0;i<n;i++)
        cout<<a[i]<<endl;

    return 0;
}