#include<fstream>
#include<vector>
#define DIM 1000000
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int w[DIM + 5],t,a,b;
vector<int> v[8];
void f(){
    w[1] = w[0] = 0;
    for( int i = 2; i <= DIM; i++ ){
        if( w[i] == 0 ){
            w[i] = 1;
            for( int j = i + i; j <= DIM; j += i ){
                w[j]++;
            }
        }
    }
    return;
}
int g( int k, int n ){
    int st = 0;
    int dr = v[k].size() - 1;
    while( st <= dr ){
        int mid = ( st + dr ) / 2;
        if( v[k][mid] <= n ){
            st = mid + 1;
        }else{
            dr = mid - 1;
        }
    }
    if( v[k][dr] <= n ){
        return v[k][dr];
    }else{
        return 0;
    }
}
int main(){
    f();
    for( int i = 2; i <= DIM; i++ ){
        if( w[i] <= 7 )
            v[ w[i] ].push_back( i );
    }
    fin >> t;
    for( ; t != 0; t-- ){
        fin >> a >> b;
        if( b == 0 ){
            fout << "1\n";
        }else{
            fout << g( b, a ) << "\n";
        }
    }
    return 0;
}