#include <fstream>

using namespace std;

const int N = 1000001;
short  int nrd[N];

void div()
{
    int i, j;
    for ( i = 2; i < N; i++ )
        if( nrd[i] == 0 )
            for ( j = i; j < N; j += i )
                nrd[j]++;
}

int a[8][500000], nr[8];

void matrice()
{
    int j, d;
    for ( j = 1; j < N; j++ ){
        d = nrd[j];
        a[d][++nr[d]] = j;
    }
}

int cautare( int x, int y )
{
    int pas, i = 0;
    pas = 1 << 19;
    while( pas != 0 )
    {
        if ( i + pas <= nr[y] && a[y][i + pas] <= x )
            i+=pas;
        pas/=2;
    }
    return i;
}

int main()
{
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    int t, i, n, d, j, aux;
    div();
    matrice();
    in >> t;
    for ( i = 1; i <= t; i++ )
    {
        in >> n >> d;
        aux = cautare( n, d);
        out << a[d][aux]<< '\n';
    }
    return 0;
}