#include <fstream>

using namespace std;

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

int main()
{
    int t, n, k, a, i, cnt, d, ci, ok;
    cin>>t;
    for(a=1;a<=t;a++)
    {
        cin>>n>>k;
        i=n;
        ok=0;
        while(i>1 && ok==0)
        {
            d=2;
            ci=i;
            cnt=0;
            while(ci>1)
            {
                if(ci%d==0)
                {
                    cnt++;
                    while(ci%d==0)
                        ci/=d;
                }
                d++;
            }
            if(cnt==k)
                ok=1;
            else
                i--;
        }
        if(i==1)
            cout<<0<<'\n';
        else
            cout<<i<<'\n';
    }
    return 0;
}