#include<stdio.h>

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

struct nod
{ int n,k;
} b[100001];
int prelucrare(int x,int y)
{     
  int st, dr,ok=0,mij;
      if(mat[y][1]==0) 
      { printf("0\n");
        return 0;
      }
      else
       { st=1;
         dr=mat[y][0];
             while(st<=dr&&!ok)
                   { mij=(st+dr)/2;
                     if(mat[y][mij]==x) ok=1;
                     else if(mat[y][mij]<x) st=mij+1;
                     else dr=mij-1;
                   }
              while(mat[y][mij]>x) mij--;     
              printf("%d\n",mat[y][mij]);
        }
   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]++;
                        mat[a[i]][++mat[a[i]][0]]=i;
                      }   
  
    for(i=1;i<=t;i++) prelucrare(b[i].n,b[i].k);
    
  fclose(stdin);
  fclose(stdout);
  return 0;
  
}