#include <fstream>

using namespace std;

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

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