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

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 k, int x)
{
    int mid, save = -1 ;
    while ( st <= dr )
    {
        mid = (st+dr) /2;
        if ( x > p[k][mid] ) st = mid +1; else dr = mid -1;
        if ( x >= p[k][mid] ) save = mid;
    }
    if ( save == -1 ) return 0;
return p[k][save];
}

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

  for ( int i=1; i<=maxim-9; i++)
       p[ a[i] ][++p[a[i]][0]] = i;

    while ( t-- )
    {
        in >> x >> y;
     out << caut(1,p[y][0],y,x) << '\n';
    }

    return 0;
}