#include <fstream>
#include <cmath>
using namespace std;
short v[1000001];
int  a[8][1000001];
void completam(int i)
{
    int j;
    for(j=i;j<=1000000;j+=i)
    {
        v[j]+=1;
        //a[v[j]][j]=j;
    }
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int t,n,k,r,i,j;
    //r=1000;
    completam(2);
    for(i=3;i<=500000;i+=2)
    {
        if(v[i]==0)
            completam(i);
    }
    for(i=500001;i<=1000000;i+=2)
     {
         if(v[i]==0)
            v[i]=1;
      //  a[v[i]][i]=i;
     }
     for(i=2;i<=1000000;i++)
     {
         a[v[i]][i]=i;
         for(j=1;j<=8;j++)
            if(a[v[j]][i]==0)
                a[v[j]][i]=a[v[j]][i-1];
     }
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
     /*   if(k==0)
            g<<"1"<<'\n';
        else
        {
            j=n;
            while(v[j]!=k and j>1)
            {
                j-=1;
            }
            if(j>1)
                g<<j<<'\n';
            else
                g<<"0"<<'\n';

        }*/
        /*for(j=n;j>=1;j-=1)
        {
            if(a[k][j]!=0)
            {
                g<<j<<'\n';
                j=-1;
            }
        }
        if(j==0) g<<"0"<<'\n';*/
            g<<a[k][j]<<'\n';
    }
 /*  for(i=1;i<=10;i++)
        g<<v[i]<<" "<<i<<'\n';*/
      /*for(i=1;i<=7;i++)
        {
            for(j=1;j<=20;j++)
                g<<a[i][j]<<" ";
            g<<'\n';
        }*/
    f.close();
    g.close();
    return 0;
}