#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");

int prim (int N, int K)
{
    int d,nr,cx,ab;
    for (int i=N;i>1;i--)
    {
        d=2;nr=0;cx=i;ab=i;
        while (ab!=1)
    {
        if (ab%d==0)
        {
            while(ab%d==0)
                ab/=d;
            nr++;
        }
        d++;
    }
    if (nr==K)
        return cx;
    }
    return 0;
}

int main()
{
    int N,K,T;
    f>>T;
    for (int j=0;j<T;j++)
    {
        f>>N>>K;
        g<<prim(N,K)<<endl;
    }
    return 0;
}