#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int main()
{
    int t,a,k,n,cnt=0,d=2,p=0,ok=0;
    fin>>t;
    for(int i=0; i<t; i++)
    {
        fin>>a>>k;
        for(int j=a; j>=0; j--)
        {
            n=j;
            d=2;
            cnt=0;
            while(n>1)
            {
                p=0;
                while(n%d==0)
                {
                    p++;
                    n=n/d;
                }
                if(p>0)
                {
                    cnt++;
                }
                d=d+1;
                if(n>1 && d*d>n)
                {
                    d=n;
                }
            }
            if(cnt==k)
            {
                fout<<j<<endl;
                ok=1;
                break;
            }
            cnt=0;
        }
        if(ok==0)
            fout<<0<<endl;
        ok=0;
    }
    return 0;
}