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

int main(){

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

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

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

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

     for(j=2;j<=n&&ok;j++){
      if(v[j]==0){
	for(j2=j;j2<=n&&ok;j2+=j){
	v[j2]++;


	}

      }

     }

     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);

     for(j=2;j<=n;j++){
     v[j]=0;
     }

   }

fclose(f);
fclose(g);

return 0;
}