#include <fstream>

using namespace std;
ifstream cin ("divprim.in");
ofstream cout ("divprim.out");
short int v[1000001];
int v1[100001];
short int v2[100001];
int main()
{
    int t,n,k,max=0,i,j;
    cin>>t;
    for (i=1;i<=t;i++)
    {
        cin>>v1[i]>>v2[i];
        if (v1[i]>max)
        max=v1[i];
    }
    for (i=2;i<=max;i++)
    {
        if (v[i]==0)
        {
            for (j=i;j<=max;j+=i)
            v[j]++;
        }
    }
    for (i=1;i<=t;i++)
    {
        n=v1[i];
        k=v2[i];
        for (j=n;j>=1;j--)
        if (v[j]==k)
        {
            cout<<j<<endl;
            j=-1;
        }
        if (j==0)
        cout<<0<<endl;
    }

    return 0;
}