/// Nume; Misăilă Vlad
/// Scoala: Colegiul National Gr. Moisil
/// Clasa: a X-a
/// mail: [email protected]

#include <fstream>
using namespace std;

int prop(int x,int div)
{
    int pr=0, d=2;
    while(x!=1)
    {
        if(x%d==0)
        {
            pr++;
            if(pr>div)
                return 0;
            while(x%d==0)
                x/=d;
        }
        d++;
    }
    if(pr==div)
        return 1;
    return 0;
}

int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int n;
    fin >> n;
    int a[2][n];
    for(int i=0; i<n; i++)
        fin >> a[1][i] >> a[2][i];

    for(int i=0; i<n; i++)
        {
            int ok=1;
            while(ok&&a[1][i]>0)
            {
                if(prop(a[1][i],a[2][i])==0)
                    a[1][i]--;
                else
                    ok=0;
            }
            fout << a[1][i] << "\n";
        }

    return 0;
}