#include <cstdio>
#include <cmath>
#define maxn 1000005

bool prime[maxn];
int primes[maxn], np;
int n, K;


void gen()
{
  int i, j, m=(int)sqrt(maxn)+1;
  prime[1]=1;
  for(i=4;i<maxn;i+=2) prime[i]=1;

  for(i=3;i<=m;i++)
    if(!prime[i])
      for(j=i+i;j<maxn;j+=i) prime[j]=1;

  for(i=2;i<maxn;i++)if(!prime[i]) primes[++np]=i;
}

int main()
{
  gen();
  freopen("divprim.out", "w", stdout);
  freopen("divprim.in", "r", stdin);
  int T, i, j,k, poz;
  scanf("%d\n", &T);
  for(i=1;i<=T;i++)
    {
      scanf("%d %d\n", &n, &K);
      int sol=0;
      for(j=n;j>=1;j--)
	{
	  int nr=0;
	for(k=1;k<=np;k++)
	  {
	    if(primes[k]>(n>>1)) break;
	    if(j%primes[k]==0) nr++;
	  }
	if(nr==K) { sol=j;break;}
	}
      printf("%d\n", sol);
    }
  return 0;
}