#include<fstream.h>

long long t, n, k, m[9][1000004], 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;

}
/*
# int binary_search(int val)  
# {  
#     int i, step;  
#     for (step = 1; step < N; step <<= 1);  
#     for (i = 0; step; step >>= 1)  
#         if (i + step < N && A[i + step] <= val)  
#            i += step;  
#     return i;  
# }  
*/

void calcul()
{
  int j;
  in>>n>>k;
  if (m[k][1]>n) out<<"0"<<'\n';
    else if (k==0) out<<"1"<<'\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;
  int i, j;
  ciur(1000004);
  mat();
  for (i=1; i<=t; i++) calcul();
  in.close();
  out.close();
  return 0;
}