#include <fstream>

using namespace std;

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

int t,n,i,d[1000001],x,k,j;
bool ok;
int main()
{
    d[1]=0;
    for(i=2;i<=1000000;++i)
    if(d[i]==0)
    for(j=1;i*j<=1000000;++j) d[i*j]++;
    f>>t;
    for(i=1;i<=t;++i)
    {
        f>>x>>k;
        ok=0;
        for(j=x;j>=1 && ok==0;--j)
        if(d[j]==k)
        {
            ok=1;
            g<<j<<"\n";
        }
        if(ok==0) g<<"0"<<"\n";
    }
}