#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
#define Max 1000001
int n,k,t,v[Max];


void precompute ()
{
  for (int i=2; i<=Max; i++)
	if (v[i]==0)
	  for (int j=i; j<=Max; j += i )
		v[j]++;
}
  
int find_nr (int n, int k)
{
  for (int i=n; i>=1; i--)
	if (v[i]==k)
	  return i;
  return 0;
}

int main ()
{
  precompute ();
  f>>t;
  for (int i=1; i<=t; i++)
  {
	f>>n>>k;
	if (n==1) g<<0<<'\n';
	else g<<find_nr (n,k)<<'\n';
  }
  f.close (); g.close ();
  return 0;
}