#include <algorithm>
#define DIM 1000001

using namespace std ;

int a[DIM][8] ;
int phi[DIM] ;
bool ciur[DIM] ;

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

  for (int i=2 ; i<=DIM ; ++i) {
    if (ciur[i]==0) {
      for (int j=i ; j<=DIM ; j+=i ) {
        ciur[j]=1 ;
        phi[j]++ ;
      }
    }
  }

  for (int i=1 ; i<DIM ; ++i) {
    for (int j=1 ; j<=7 ; ++j ) {
      if (phi[i]!=j)
        a[i][j]=a[i-1][j] ;
      else a[i][j]=i ;
    }
  }

  int t ;
  scanf ("%d" , &t) ;
  for (int i=1 ; i<=t ; ++i) {
    int x, y ;
    scanf ("%d%d" , &x , &y) ;
    printf ("%d\n" , a[x][y]) ;
  }

  return 0 ;
}