#include <fstream>

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

int nrdivizprimi(int x)
{
    int nr=0, d=2, e=0;
    while(x%d==0)
    {
        x/=d; e++;
    }
    if(e>1)
        nr++;

    for(d=3; d*d<=x; d+=2)
    {

        e=0;
        while(x%d==0)
        {
            x/=d; e++;
        }
        if(e>1)
            nr++;


    }
    return nr;
}

int main()
{
    int N, K, T;
    f>>T;
    while(T)
    {
        f>>N>>K;
        int valmax=N;
        while(valmax>-1)
        {
            if(nrdivizprimi(valmax)==K)
            {
                g<<valmax<<"\n"; break;
            }
            else
                valmax--;
            if(valmax==0)
            g<<0;
        }

        T--;
    }

    return 0;
}