#include<stdio.h>

int a[1000001],i,j,t;

int prelucrare()
{ 
     int n,k,i;
     scanf("%d %d",&n,&k);     
      for(i=n;i>=2;--i) if(a[i]==k) { printf("%d\n",i);
                                       return 0;
                                     }
      printf("0\n");
      return 0;
}                
                 
int main()
{ freopen("divprim.in","r",stdin);
  freopen("divprim.out","w",stdout);
  
  for(i=2;i<=1000000;i++) if(!a[i]) for(j=i;j<=1000000;j+=i) a[j]++;
  scanf("%d",&t);
  for(i=1;i<=t;i++) prelucrare();
  
  fclose(stdin);
  fclose(stdout);
  return 0;
  
}