#include<iostream.h>
#include<stdio.h>

  long long a[1000];

  long long prim(long long n)
  { long long i;
      for(i=2;i*i<=n;i++)
       if(n%i==0)
	 return 0;
	 return 1;
  }


   long long nrdiv(long long n)
   {
     long long i,s=0;
      for(i=2;i*2<=n;i++)
       { if(n%i==0 && prim(i)==1)
	   s++;
       }
      return s;
   }


  int main()
{
   long long x, n, k, t=0, j, i;

freopen("divprim.in", "r", stdin);
freopen("divprim.out", "w", stdout);

scanf("%lld", &x);

for(i=1;i<=x;i++)
{ cin>>n>>k; t=0; 
    for(j=n-1;j>=0;j--)
     { if(nrdiv(j)==k)
	{ a[i]=j;
	 t=1;
	}
       if(t)
        break;
     }

}    

  for(i=1;i<=x;i++)
  { printf("%lld\n", a[i]); }


return 0;
}