#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
 
int t;
const int maxn = 1e6, maxt = 1e5;
int d[ maxn + 10 ];
int ciur[ maxn + 10 ];
int D[ 100 ][ maxn + 10 ];
//int ina[ maxt + 10 ], inb[ maxt + 10 ], out[ maxt + 10 ];
//int frec[ maxn ];
 
int main() {
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    g.tie(nullptr);
 
    f >> t;
    d[1] = 0;
    int lim = 1e6;
    for( int i = 2; i <= maxn/5; ++i )
    {
        if( ciur[ i ] == false )
        {
            for( int j = i*2; j <= maxn; j+=i )
            {
                ciur[ j ] = true;
                ++d[ j ];
            }
        }
        //++D[ d[i] ][0];
        //D[ d[i] ][ D[ d[i] ][0] ] = i;
    }
    for( int i = 2; i <= maxn; ++i )
    {
        if( ciur[ i ] == false )
            ++d[i];
        ++D[ d[i] ][0];
        D[ d[i] ][ D[ d[i] ][0] ] = i;
    }
 
    for( int i = 1; i <= t; ++i )
    {
        int a, k, ras = 0;
        f >> a >> k;
        int st = 1, dr = D[k][0], mij;
        //for( int i = 1; i <= D[k][ D[k][0] ]; ++i )
        //    g << D[k][i] << " ";
        while( st <= dr )
        {
            mij = st + (dr-st)/2;
            if( D[k][ mij ] == a )
            {
                ras = a;
                break;
            }
            else if( D[k][mij] < a )
                ras = D[k][mij], st = mij + 1;
            else if( D[k][mij] > a )
                dr = mij - 1;
        }
        g << ras << "\n";
    }
    return 0;
}