#include <fstream>
#define N 1000000
using namespace std;

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

int c[N+5],a[8][400000],div[N+1];

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

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

void Parcurgere()
{ int i;
  for(i=1;i<=1000000;i++)
     if(div[i]==1) {j1++; a[1][j1]=i;}
     else if(div[i]==2) {j2++; a[2][j2]=i;}
     else if(div[i]==3) {j3++; a[3][j3]=i;}
     else if(div[i]==4) {j4++; a[4][j4]=i;}
     else if(div[i]==5) {j5++; a[5][j5]=i;}
     else if(div[i]==6) {j6++; a[6][j6]=i;}
     else if(div[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<=t;i++)
        { fin>>x>>y;
          fout<<CB(1,a[y][0],x,y)<<"\n";
        }

    return 0;
}