#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

#define N 1000000
int c[N+5],a[8][400000],divv[N+5];

int j1,j2,j3,j4,j5,j6,j7;

void Ciur()
{ int i,j;int k=0;
  c[2]=1;
  for(i=3;i<=N;i=i+2)
     c[i]=1;
  for(i=2;i<=N;i++)
     if(c[i]==1)
        { k++;
            for(j=i;j<=N;j=j+i)
           { if(j!=i)
             c[j]=0;
             divv[j]++;
           }
        }
  // cout<<k;
}

void Parcurgere()
{ int i;
//cout<<j1;
  for(i=2;i<=N;i++)
     if(divv[i]==1) {j1++; a[1][j1]=i;}
     else if(divv[i]==2) {j2++; a[2][j2]=i;}
     else if(divv[i]==3) {j3++; a[3][j3]=i;}
     else if(divv[i]==4) {j4++; a[4][j4]=i;}
     else if(divv[i]==5) {j5++; a[5][j5]=i;}
     else if(divv[i]==6) {j6++; a[6][j6]=i;}
     else if(divv[i]==7) {j7++; a[7][j7]=i;}

  a[1][0]=j1;
  a[2][0]=j2;
  a[3][0]=j3;
  a[4][0]=j4;
  a[5][0]=j5;
  a[6][0]=j6;
  a[7][0]=j7;
}

int CB(int s,int d,int x,int y)
{ int m;
  while(s<=d)
    { m=(s+d)/2;
      if(x==a[y][m]) return x;
      else if(x<a[y][m]) d=m-1;
      else s=m+1;
    }

    if(a[y][s]<x) return a[y][s];
    if(s-1!=0) return a[y][s-1];
    else return 0;


}


int main()
{   int i,t,ct,j,m=0,x,y;
    Ciur();
    Parcurgere();
    fin>>t;

//    for(i=1;i<=30;i++)
  //     fout<<divv[i]<<" ";

    //fout<<"\n";
  /*  for(i=1;i<=7;i++)
       { for(j=1;j<=5;j++)
             fout<<a[i][j]<<" ";
         fout<<"\n";
       }

*/
    for(i=1;i<=t;i++)
        { fin>>x>>y;
          fout<<CB(1,a[y][0],x,y)<<"\n";
        }

    return 0;
}