#include<fstream>
#include<algorithm>
using namespace std;
 
int i,j,a[1000005][15];
int b[1000005],n,k,m;
 
int main()
{
  ifstream fin("divprim.in");
  ofstream fout("divprim.out");
 
  for(i=2;i<=1000000;i++)
  if(!b[i]){ 
  for(b[i]=1,j=2*i;j<=1000000;j=j+i){ b[j]++;  
  }
  
  }
 
  for(i=1;i<=1000000;i++)
  {
    for(j=0;j<=14;++j) 
	a[i][j]=a[i-1][j];
    a[i][b[i]]=i;
  }
 
  fin>>m;
 
  while(m--)
  fin>>n>>k;
  fout<<a[n][k]<<'\n';
 
 return 0;
}