#include <bits/stdc++.h>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int maxim = 1000009;
int a[maxim], prim[maxim] ;
bool v[maxim];
pair < int, int > p[maxim];

bool cmp( pair < int, int > a, pair < int, int > b)
{
    if ( a.first == b.first ) return a.second <b.second;
         else return a.first < b.first;
}

void ciur()
{
    for(int i=2; i<=maxim-9; i++)
    {
        if( !v[i] )

            for(int j=i; j<=maxim-9; j+=i)
                v[j] = 1, a[j]++ ;
    }

}

int caut( int st, int dr, int x, int n)
{
   int mid, save = 0;
   while ( st<= dr )
   {
       mid = (st+dr)/2;
       if ( x> p[mid].first ) st = mid +1; else dr = mid -1;
       if ( x <= p[mid].first ) save = mid;
   }
 int  left = save; save=0; dr= maxim-9; st = 1;
   while ( st <=dr )
   {
       mid = (st+dr) /2;
       if ( x>=p[mid].first ) st = mid +1; else dr = mid -1;
       if ( x == p[mid].first ) save = mid;
   }
   int right = save; save = 0;

   while ( left <= right  )
   {
       mid = ( left+right ) /2;
       if ( n > p[mid].second ) left = mid +1; else right = mid -1;
        if ( n >= p[mid].second ) save = mid;
   }
   return p[save].second ;
}

int main()
{
    ciur();
    int t, x, y; in >> t;

  for ( int i=1; i<=maxim-9; i++)
  {
      p[i].first = a[i];
      p[i].second = i;
  }
  sort(p+1,p+maxim-8, cmp);

    while ( t-- )
    {
        in >> x >> y;
        out << caut(1,maxim-8,y,x) << '\n';
    }


    return 0;
}