#include<fstream.h>

long long t, n, k, c[1000000], v[100000];


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

int verif(long long x)
{
  int i, contor=0;
  for (i=1; i<=x; i++)
    if (x%v[i]==0) contor++;
  return contor;
}

int main()
{
  ifstream in("divprim.in");
  ofstream out("divprim.out");
  in>>t;
  int i, j;
  ciur(1000000);
  for (i=1; i<=t; i++)
    {
      in>>n>>k;
      for (j=n; j>=1; j--)
	if (verif(j)==k) break;
      out<<j<<'\n';
    }
  return 0;
}