#include<fstream.h>

long long t, n, k, nr1, nr2, nr3, nr4, nr5, nr6, nr7,m[8][700000];
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;
  nr1=nr2=nr3=nr4=nr5=nr6=nr7=0;
  for (i=1; i<=n; 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;}
	 }

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

}

void calcul()
{
  int j;
  in>>n>>k;
  ciur(n);
  mat();
  if (m[k][1]>n) out<<"0"<<'\n';
    else {
      for (j=m[k][0]; j>=1; j--)
	if (m[k][j]<=n) break;
      out<<m[k][j]<<'\n';}
}


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