#include <fstream>
#define L 1000003
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,prim[L],M[8][L],j,i,step,t,q,K,v;
void bag(int val,int nu)
{
  if (nu<=7)
    {
      M[nu][0]++;
      M[nu][M[nu][0]]=val;
    }
}
int caut(int val,int k)
{
  int STEP=1,  en=M[k][0];
  for(; STEP*2<en; STEP*=2);
  for(j=0; STEP; STEP/=2)
    if (M[k][j+STEP]<=val&&j+STEP<=en) j+=STEP;
if (j==0) return 0; else
  return M[k][j];
}
int main()
{
  for(i=2; i<L; i++) if (prim[i]==0)
      for(j=i; j<=L-3; j+=i) prim[j]++;



  for(i=1; i<=L-4; i++) bag(i,prim[i]);

  f>>t;

  for(q=1; q<=t; q++)
    {
      f>>n>>K;
      g<<caut(n,K)<<'\n';
    }


  f.close();
  g.close();
  return 0;
}