#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
int nmax=1000000;
     int n,v[1000000]={},nr[100000][4];
     int a[1000000]={},mx,m;
int caut (int s,int d,int x)
{
    if(s>d)
        return 0;
    else
        {
            m =(s+d)/2;
            if (x>=a[m]){

                  mx=m;
                return caut(m+1,d,x);
            }
            if (x<a[m])
                return caut(s,m-1,x);
            else
                return caut(m+1,d,x);
        }
}

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){
                a[i]++;
             for(int j=2*i;j<nmax;j+=i){
                 v[j]=1;
                a[j]++;
             }
          }

int i;
int mn,k,man,j;
int nmx=10000;
/*for (i=1;i<=nmx;i++){
 mn=a[i];
 k=i;
 for (j=i+1;j<=nmx;j++)
 if (a[j]<mn){
 mn=a[j];
 k=j;
}
 man=a[k];
 a[k]=a[i];
 a[i]=man;

 }
 */
 int c=0;
 cout<<nr[1][2];
   for(int j=1;j<=n;j++){
        c=0;
 for(int i=nr[j][1];i>=2;i--){
       if(a[i]==nr[j][2]){
            g<<i<<"\n";
            c=1;
               break;
       }


 }
 if(c==0)
       {
           g<<0<<"\n";
       }
   }






        // g<<nrm<<"\n";

          return 0;
}