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

using namespace std;

    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
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 c_bin(int x, int ka, int low, int high )
{
int mid;
while (low<=high)
     {
         mid=low+(high-low)/2;
         if (x<mat[mid][ka]) high=mid-1;
         else if (x>mat[mid][ka]) low=mid+1;
         else return mid-1;
     }
     
     if(mat[high-1][ka] < x) return high-1;
     else return mid-1;    
}


void Cauta(int nr, int k)
{
    
  if(k==1)
   {
     int p = c_bin(nr,k,0,i1-1);
     fout<<mat[p+1][k]<<endl;              
   }
   else if(k==2)
   {
     int p = c_bin(nr,k,0,i2-1);    
      fout<<mat[p+1][k]<<endl;      
   }
   else if(k==3)
   {
     int p = c_bin(nr,k,0,i3-1);
     fout<<mat[p+1][k]<<endl;    
   }
   else if(k==4)
   {     
     int p = c_bin(nr,k,0,i4-1);
     fout<<mat[p+1][k]<<endl;  
   }
   else if(k==5)
   {     
     int p = c_bin(nr,k,0,i5-1);
     fout<<mat[p+1][k]<<endl;  
   }      
   else if(k==6)
   { int p = c_bin(nr,k,0,i6-1);
     fout<<mat[p+1][k]<<endl;    
   }
   else if(k==7)
   {     
     int p = c_bin(nr,k,0,i7-1);
     fout<<mat[p+1][k]<<endl;    
   }
   else if(k==8)
   {     
     int p = c_bin(nr,k,0,i8-1);
     fout<<mat[p+1][k]<<endl;    
   }   
}

using namespace std;

int main(int argc, char *argv[])
{    
    mat[i1][1]=2;i1++;
    mat[i1][1]=3;i1++; 
    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++) 
    {        
    Cauta(vt[i][0],vt[i][1]);        
    }   
    fout.close();
    fin.close();
    return EXIT_SUCCESS;
}