#include <iostream>
#include <stdio.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 mat[1000000][8]={};
int main()
{

FILE * pFile;
 pFile=fopen("divprim.in","r");
fscanf(pFile,"%d",&n);




   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]++;
             }

          }
             for(int j=1;j<=8;j++)
                 mat[i][j]=mat[i-1][j];
                    mat[i][a[i]]=i;
   }

int i;
int mn,k,man,j;


 FILE * pF=fopen("divprim.out","w+");;
 int c,c1;



   for(int j=1;j<=n;j++){
              fscanf(pFile,"%d",&c);
              fscanf(pFile,"%d",&c1);
              fprintf(pF,"%d   \n",mat[c][c1]);
          }








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

          return 0;
}