#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

int t, ciur[1000001];
int i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0;
int mat[1000001][9];

void Ciur(int n)
{
  for(int i=2;i<=(n/2);i++)
      for(int j=2;(j*i)<=n;j++)
        ciur[j*i]=1;
//  for (int i=2;i<=n;i++) cout << ciur[i] << " ";   
}

int Cauta(int nr, int k)
{
  int nrC=0;  
  if(k==1)
   {
     int c=0;
     while(c<=i1)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i1+1;
       }
       c++;         
     }     
   }
   else if(k==2)
   {
     int c=0;
     while(c<=i2)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i2+1;
       }
       c++;         
     }     
   }
   else if(k==3)
   {
     int c=0;
     while(c<=i3)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i3+1;
       }
       c++;         
     }     
   }
   else if(k==4)
   {
     int c=0;
     while(c<=i4)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i4+1;
       }
       c++;         
     }     
   }
   else if(k==5)
   {
     int c=0;
     while(c<=i5)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i5+1;
       }
       c++;         
     }     
   }      
   else if(k==6)
   {
     int c=0;
     while(c<=i6)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i6+1;
       }
       c++;         
     }     
   }
   else if(k==7)
   {
     int c=0;
     while(c<=i7)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i7+1;
       }
       c++;         
     }     
   }
   else if(k==8)
   {
     int c=0;
     while(c<=i8)
     {
       if(mat[c][k]>nrC && mat[c][k]<=nr)
       {
         nrC=mat[c][k];
         if (nrC==nr) c=i8+1;
       }
       c++;         
     }     
   }
return nrC;   
}

using namespace std;

int main(int argc, char *argv[])
{    
    ifstream fin("divizori.in");
    ofstream fout("divizori.out");
    int t;
    int vt[100001][2];
    fin >> t;
    int max=0;
    for(int ct=0;ct<t;ct++)
    {
     fin >> vt[ct][0] >> vt[ct][1];
     if (max<vt[ct][0]) max=vt[ct][0];       
    }            
    Ciur(max+1);   
    for(int i=2;i<=max+1;i++)
    {
      int aux=0;      
      for(int j=2;j<=i/2;j++)
      {
       if(ciur[j]==0 && i%j==0)
       {
        aux++;             
       }        
      }
      switch(aux)
      {                 
        case 1:
             {
               mat[i1][1]=i;
               i1++;         
             }
             break;
        case 2:
             {
               mat[i2][2]=i;
               i2++;         
             }
             break;
        case 3:
             {
               mat[i3][3]=i;
               i3++;         
             }
             break;
        case 4:
             {
               mat[i4][4]=i;
               i4++;         
             }
             break;
        case 5:
             
             {
               mat[i5][5]=i;
               i5++;         
             }
             break;
        case 6:
             {
               mat[i6][6]=i;
               i6++;         
             }
             break;
        case 7:
             {
               mat[i7][7]=i;
               i7++;         
             }
             break;
        case 8:
             
             {
               mat[i8][8]=i;
               i8++;         
             }
             break;                               
      }
    }
    for (int i=0;i<t;i++) fout<<Cauta(vt[i][0],vt[i][1])<<"\n";
    fout.close();
    fin.close();
    return EXIT_SUCCESS;
}