#include <iostream>
#include <fstream>
using namespace std;
int nmax=1000002;
     int n,v[1000000]={},nr[100000][4];

int main()
{
ifstream f("divprim.in");
ofstream g("divprim.out");
f>>n;
for(int i=1;i<=n;i++)
  {
      f>>nr[i][1];
      f>>nr[i][2];
  }

   for(int i=2;i<=nmax;i++)
          if(v[i]==0)
             for(int j=2*i;j<=nmax;j+=i)
                 v[j]=1;

int i,nrm;
  for(int gs=1;gs<=n;gs++){
    int c=0,k=0;
         for(i=nr[gs][1];i>=nr[gs][2]&&c!=nr[gs][2];i--){
                c=0;
               for(int j=i/2;j>=2;j--)
         {
             if(v[j]==0&&i%j==0){
                   c++;
                   nrm=i;

                     //break;
             }



         }
          if(i==nr[gs][2]&&c!=nr[gs][2])
             {
                 i=1;
                 nrm=0;
                 break;
             }

         }
         g<<nrm<<"\n";
}
          return 0;
}