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

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

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/i;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;
  }

  cin>>t;

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

 return 0;
}