#include<fstream.h>

long long t, n, k, m[9][700004], nr1, nr2, nr3, nr4, nr5, nr6, nr7, nr8;
int *c=new int[1000004];

ifstream in("divprim.in");
ofstream out("divprim.out");

void ciur(int n)
{
  int i, j;
  for (i=2; i<=n; i++)
    {
       if (c[i]==0)
	{ c[i]=1;
	  for (j=2*i; j<=n; j+=i)
		c[j]++;
	}
    }
}

void mat()
{
  long long i;
  for (i=1; i<=1000004; i++)
    {
       switch(c[i])
	 {
	   case 1: { nr1++; m[1][nr1]=i;break;}
	   case 2: { nr2++; m[2][nr2]=i;break;}
	   case 3: { nr3++; m[3][nr3]=i;break;}
	   case 4: { nr4++; m[4][nr4]=i;break;}
	   case 5: { nr5++; m[5][nr5]=i;break;}
	   case 6: { nr6++; m[6][nr6]=i;break;}
	   case 7: { nr7++; m[7][nr7]=i;break;}
	   case 8: { nr8++; m[8][nr8]=i;break;}
	 }

    }
  m[1][0]=nr1;
  m[2][0]=nr2;
  m[3][0]=nr3;
  m[4][0]=nr4;
  m[5][0]=nr5;
  m[6][0]=nr6;
  m[7][0]=nr7;
  m[8][0]=nr8;

}
long long cautare()
{
  long long p, u, a, ok=1, exa;
  p=1; u=m[k][0];
  a=(p+u)/2;
  while (p<=u && ok)
    {
      if (m[k][a]==n) ok=0;
	 else if (m[k][a]>n)  { u=a; a=(p+u)/2;}
	       else  { p=a; a=(p+u)/2; }
    }
  if (p>u) return m[k][u-1];
  return a;
}


void calcul()
{
  int j;
  in>>n>>k;
  if (m[k][1]>n) out<<"0"<<'\n';
    else if (k==0) out<<"1"<<'\n';
    else {
      long long rez=cautare();
      out<<rez<<'\n';}
}


int main()
{
  in>>t;
  int i, j;
  ciur(1000004);
  mat();
  for (i=1; i<=t; i++) calcul();
  in.close();
  out.close();
  return 0;
}