#include<stdio.h>
#include<string.h>
#define fin "divprim.in"
#define fout "divprim.out"

long t,n,num,remind;
int k,primes[]={2,3,5,7,11,13,17},div;

int verif(int, int);
void solve(int , int );
void ciur();

int main(void)
{
  freopen(fin,"r",stdin);
  freopen(fout,"w",stdout);

  scanf("%ld",&t);

  for(register long i=1;i<=t;i++)
  {
   scanf("%ld%ld",&num,&div);
   solve(num,div);
  }

  fcloseall();
  return 0;
}
int verif(int m,int n)
{
 if( (n==1) && (m >= primes[0]))
  return 1;
 if ((n==2) && ( m >= primes[0]*primes[1]) )
  return 1;
 if( (n==3) && (m >= primes[0]*primes[1]*primes[2]) )
  return 1;
 if( (n==4) && (m >= primes[0]*primes[1]*primes[2]*primes[3]))
  return 1;
 if( (n==5) && (m >= primes[0]*primes[1]*primes[2]*primes[3]*primes[4]))
  return 1;
 if( (n==6) && (m >= primes[0]*primes[1]*primes[2]*primes[3]*primes[4]*primes[5]))
  return 1;
 if( (n==7) && (m >= primes[0]*primes[1]*primes[2]*primes[3]*primes[4]*primes[5]*primes[6]))
  return 1;

 return 0;


}
void solve(int x, int y)
{
 if(verif(x,y))
  {
   int nrdiv=0,aux=x,sw=0,check=0;
   long i;
    while(!sw)
    {
      nrdiv=0;
      i=0;
      check=0;
      aux=x;
      while(aux>1)
       {
	k=0;
	while(!(aux%primes[i]))
	{
	 aux/=primes[i];
	  k++;
	}
	if(k)
	 ++nrdiv;
	if( ((nrdiv>=y) && (aux>1)) || i>y )
	{
	  check=1;
	  break;
	}
	else
	 ++i;
       }
      if( (!check) && (nrdiv==y))
       {
	remind = x;
	printf("%ld\n",remind );
	sw++;
       }
      else
       --x;
    }
  }
 else
  printf("%d\n",0);
}