#include<stdio.h>
int T,i,ok,n,k,j,j2,g;
int v[1000001];

int main(){

FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");

fscanf(f,"%d",&T);

  for(j=2;j<=1000000;j++){
      if(v[j]==0){
	for(j2=j;j2<=1000000;j2+=j){
	v[j2]++;
	}
      }
  }



   for(i=1;i<=T;i++){
   ok=1;

   fscanf(f,"%d %d",&n,&k);


     for(j=n;j>=2;j--){
       if(v[j]==k){
       ok=0;
       fprintf(g,"%d\n",j);
       break;
       }
     }

     if(ok)fprintf(g,"%d\n",0);



   }

fclose(f);
fclose(g);

return 0;
}