#include<stdio.h>
#define nravarie 499979
#define nrmax 1000000
int a[8][379730]; //hehe
int v[1000001];
int mic[9];
int b,a1;
int cauta(int st,int dr,int nr)
{
    
int m=(dr+st)/2;
    
 if(a[b][m] < nr && a[b][m+1] > nr){
 printf("%d\n",a[b][m]);
 return 0;}
 else
  if(a[b][m] > nr )
  cauta( st, m-1,nr); 
  else
  if(a[b][m] < nr)
  cauta( m+1, dr,nr);
    
}


int main()
{
 freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);
 
 int n,i,j;
 scanf("%d",&n);
 
   for(i=2; i<=nravarie; ++i)
    if(!v[i])
     for(j=i; j<=nrmax; j+=i)
     ++v[j];
     
     
   for(i=2; i<=nrmax; ++i)
    if( v[i] <=7 )
 {  ++mic[v[i]];
   a[ v[i] ][ mic[v[i]] ]= i;
 }
     
  while( n--){
  scanf("%d %d",&a1,&b);
  if(v[a1] == b)
   printf("%d\n",a1);
  else
   if( a[b][mic[b]]<a1)
   printf("%d\n",a[b][mic[b]]);
   else
   cauta(1,mic[b]-1,a1);
   }
  
    return 0;
}