#include<fstream.h>
//using namespace std;
ofstream fout("divprim.out");
long prime[1000001],T,N,K,matrice[1000000][8];
void gen_prime() {

	prime[1000000] = 1;
	for (long d = 3; d < 1000000; d+=2) {
		prime[d - 1]++;
		if (prime[d] == 0)     {
			for (long v= 2; v*d < 1000000; v++)
				prime[d * v]++;
		prime[d]=1;}
	}
	prime[2] = 1;                                   
}

int main(){
gen_prime();
for (long t=0;t<1000000;t++)
    matrice[t][prime[t]]=t;
ifstream fin("divprim.in");
fin>>T;
for (long i=0;i<T;i++){
  fin>>N>>K;
  long j=0;
  while (matrice[j][K]<=N)
       j++;
    if (j==0)
       if (matrice[0][K]<=N)
	  fout<<matrice[0][K]<<"\n";
    if (j!=0)
      fout<<matrice[j-1][K]<<"\n";
/*  for (long j=N;j>=0;j--)
      if (prime[j]==K){
	 fout<<j<<"\n";
	 ok=0;
	 break;}
      if (ok==1)
	 fout<<0<<"\n";    */
	 }
fout.close();
return 0;
}