#include <stdio.h>
#include <stdlib.h>
int ciur[1000000],nr[8];
int mat[8][1000000];
int caut(int v[],int n, int x){
  int i=0,pas=1<<19;
  while(pas!=0){
    if(i+pas<=n && v[i+pas]<=x)
      i+=pas;
    pas/=2;
  }
  return v[i];
}
int main()
{
  int l,d,i,k,nrdiv,nrt;
  FILE*fin,*fout;
  for(i=2;i<=1000000;i++)
    if(ciur[i]==0)
      for(d=i;d<=1000000;d+=i)
        ciur[d]++;
  ciur[1]=0;
  for(i=1;i<1000000;i++){
    nrdiv=ciur[i];
    nr[nrdiv]++;
    mat[nrdiv][nr[nrdiv]]=i;
  }
   fout=fopen("divprim.out","w");
  fin=fopen("divprim.in","r");
  fscanf(fin,"%d", &nrt);

  for(i=0;i<nrt;i++){
    fscanf(fin,"%d%d", &l, &k);
    fprintf(fout,"%d\n",caut(mat[k],nr[k],l));
  }
  fclose(fin);
  fclose(fout);
  return 0;
}