#include <fstream>
using namespace std;
const int Nmax = 5e5;
bool ciur[Nmax];
bool ok(int x,int k)
{
    int d=1,cntprim=0;
    for (d=1; d*d<x; ++d)
    {
        if (x%d==0)
        {
            if (ciur[d]==0) ++cntprim;
            if (ciur[x/d]==0) ++cntprim;
        }
        if (cntprim>k) return 0;
    }
    if (d*d==x) if (ciur[d]==0) ++cntprim;
    if (cntprim==k) return 1;
    return 0;
}
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int i,j,k,n,t,x;
int main()
{
    ciur[0]=ciur[1]=1;
    for (i = 2; i * i <= Nmax; ++i)
        if (ciur[i]==0)
            for (j = i * i; j <= Nmax; j += i)
                ciur[j] = 1;
    fin>>n;
    for (i=1; i<=n; ++i)
    {
        fin>>x>>k;
        t=0;
        for (j=x; j>=2 && t==0; --j)
        {
            if (ok(j,k)==1)
            {
                t=1;
                fout<<j<<"\n";
            }
        }
        if (t==0) fout<<"0\n";
    }

    return 0;
}