//#include<stdio.h>
//#include<iostream>
#include<fstream>
using namespace std;
int c[1000001], a[8][1000000], maxi;
void prime()
{
    c[1]=c[0]=-1;
    for(int i=1; i<=1000000; i++)
        if(c[i]==0)
            for(int j=2; i*j<=1000000; j++)
            {
                c[i*j]++;
                //if(c[i*j]>maxi)
                    //maxi=c[i*j];
            }
    for(int i=1; i<=10000; i++)// i c[i]
    {
        a[c[i]][0]++;
        int j=a[c[i]][0];
        a[c[i]][j]=i;
    }
    //for(int i=1; i<=maxi; i++)
    //{
   //     for(int j=1; j<=a[i][0]; j++) cout<<a[i][j]<<" ";
   //     cout<<endl<<endl<<endl;
   // }
}
int main()
{
    int t,n,k;
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    //FILE * f=fopen ("divprim.in", "r");
    //FILE *g=fopen ("divprim.out", "w");
    //fscanf(f,"%d", &t);
    cin>>t;
    prime();
    for(int i=1; i<=t; i++)
    {
        //fscanf(f,"%d %d", &n,&k);
        cin>>n>>k;
        if(k==0)
        {
            if(c[n]==0)
                cout<<n<<endl;//fprintf(g,"%d\n",n);
            else
            {
                n--;
                while(c[n]!=0 && n>=0)
                    n--;
                if(n>1)
                   cout<<n<<endl; //fprintf(g,"%d\n",n);
                else
                    cout<<0<<endl;

            }
        }
        else
        {
            int c1=a[k][0];
            int j=1;
            while(a[k][j]<n && j<=c1)
                j++;
            if (a[k][j]>n)
                j--;
            cout<<a[k][j]<<'\n';//fprintf(g,"%d\n",a[k][j]);
        }
    }



    return 0;
}