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

int i,j,a[1000005][15],b[1000005],n,k,m;

int main()
{
  ifstream cin("divprim.in");
  ofstream cout("divprim.out");

  for(i=2;i<=1000000;++i)
  if(!b[i]){ for(b[i]=1,j=2*i;j<=1000000;j+=i){ ++b[j]; /* cout<<b[j]<<' '<<j<<'\n';  */ }}

  for(i=1;i<=1000000;++i)
  {
    for(j=0;j<=14;++j) a[i][j]=a[i-1][j];
    a[i][b[i]]=i;
  }

  cin>>m;

  while(m--)
  cin>>n>>k,cout<<a[n][k]<<'\n';

 return 0;
}