#include <iostream>
#include <fstream>
using namespace std;
int t,i,n,k,j,nr,d,x,ok;
ofstream g("divprim.out");
int main()
{freopen ("divprim.in", "r", stdin);
scanf("%d", &t);
for (i=1; i<=t; i++)
    {scanf ("%d%d", &n, &k);
    ok=0;
    for (j=n; j>=2; j--)
        {d=2;
        nr=0;
        x=j;
        while (x!=1)
            {if (x%d==0)
                nr++;
            while (x%d==0)
                x=x/d;
            d++;}
        if (nr==k)
            {g<<j<<'\n';
            ok=1;
            break;}}
    if (ok==0)
            g<<0<<'\n';}

    return 0;
}