#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
long long aux[1000005],i,j,n,x,k,ok;
int main()
{
    for(i=2; i*i<=1000005; i++)
    {
        if(aux[i]==0)
        {
            for(j=1;i*j<=1000005;j++)
            {
                aux[i*j]++;
            }
        }
    }
    /*for(i=1;i<=100;i++)
    {
        cout<<i<<" "<<aux[i]<<endl;
    }*/
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x>>k;
        ok=0;
        for(j=x;j>=1;j--)
        {
            if(aux[j]==k)
            {
                cout<<j<<"\n";
                ok=1;
                break;
            }
        }
        if(ok==0)
        {
           cout<<0<<"\n";
        }
    }
    return 0;
}