#include<stdio.h>
#include<string.h>

#define X 1000002

int a[8][X],col[8];
char prim[X],v[X];

void bns(int st, int dr, int div, int val, int &sol)
{
 if(st>dr) return;
 int mij=st+(dr-st)/2;
 if(a[div][mij]<=val)
 {
  sol=a[div][mij];
  if(mij+1<=dr) bns(mij+1,dr,div,val,sol);
 }
 else bns(st,mij-1,div,val,sol);
}

int main()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);

 int n,val,div,sol,i,j;

 for(i=2; i<=X; i+=2) ++v[i];
 for(i=3; i<=X; i+=2)
 if(!prim[i])
 {
  ++v[i];
  for(j=i*2; j<=X; j+=i) prim[j]=1,++v[j];
 }
 for(i=1; i<=X; ++i) a[v[i]][++col[v[i]]]=i;

 scanf("%d",&n);
 for(; n; --n)
 {
  sol=0;
  scanf("%d %d",&val, &div);
  bns(1,col[div],div,val,sol);
  printf("%d\n",sol);
 }

 return 0;
}