#include <bits/stdc++.h>
#define LIMIT 1e6 

using namespace std;

int T,N,K;
int divi[1000005], precalc[1000005][10];
void nrDivizori()
{
  for(int d=2; d<=LIMIT;d++)
  {
    if(divi[d]==0)
    {
      for(int nr=d;nr<=LIMIT;nr+=d)
      {
        divi[nr]++;
      }
    }
  }
}

void precalculare()
{
  for(int nr=2;nr<=LIMIT;nr++)
  {
    for(int i=0;i<=7;i++)
    {
      precalc[nr][i]= precalc[nr-1][i];
    }
    precalc[nr][divi[nr]]=nr;
  }
}

int main() 
{
    ifstream cin ("divprim.in");
    ofstream cout("divprim.out");
    
    nrDivizori();
    precalculare();
    cin>>T;
    while(T--)
    {
      cin>>N>>K;
      cout<<precalc[N][K]<<'\n';
    }
    return 0;
}