#include<fstream.h>
long prime[1000001],T,N,K;
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 < 100000; v++)
				prime[d * v] = 1;
	}
	prime[2] = 0;
}
int danu(long N,long K){
for (long i=N;i>=0;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++;
   if (nr==K)
	return i;}
 return 0;
}
int main(){
ifstream fin("divprim.in");
fin>>T;
ofstream fout("divprim.out");
gen_prime();
for (long i=0;i<T;i++){
    fin>>N>>K;
    fout<<danu(N,K)<<"\n";}
fin.close();
fout.close();
return 0;
}