#include<stdio.h>

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

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