#include<fstream.h>
long prime[100000],a[100000];
void gen_prime() {

	prime[1000000] = 1;
	for (long d = 3; d < 1000000; d+=2) {
		prime[d - 1] = 1;
		if (prime[d] == 0)
			for (long v= 2; v*d < 1000000; v++)
				prime[d * v] = 1;
	}
	prime[2] = 0;
}
void danu(){
for (long j=0;j<=2000;j++)
for (long i=j*500;i<j*500+500;i++){
   long x=i,nr=0;
   if (x%2==0)
      nr=1;
   for (long d=3;d<=x;d+=2)
      if (prime[d]==0)
	if (x%d==0)
	  nr++;
   a[i]=nr;}
}
int main(){
long N,T,K;
gen_prime();
danu();
ifstream fin("divprim.in");
ofstream fout("divprim.out");
fin>>T;
for (long i=0;i<T;i++){
  fin>>N>>K;
  short ok=1;
  for (long j=N;j>=0;j--)
     if (a[j]==K){
	fout<<j<<"\n";
	ok=0;
	break;}
  if (ok==1)
     fout<<0<<"\n";}
fout.close();
fin.close();
return 0;
}