#include<fstream.h>
long prime[10001],T,N,K;
void gen_prime() {

	prime[10000] = 1;
	for (long d = 3; d < 10000; d+=2) {
		prime[d - 1] = 1;
		if (prime[d] == 0)
			for (long v= 2; v*d < 10000; 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;d+=2)
      if (prime[d]==1)
	if (x%prime[d]==0)
	  nr++;
   if (prime[x]==1)
      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;
}