#include <fstream>
#include <vector>
using namespace std;

ifstream cin ("divprim.in");
ofstream cout ("divprim.out");

vector <int> optiuni[8];
int numar_factori[1000001];

int main ()
{
    optiuni[0].push_back(1);
    for (int valoare = 2 ; valoare <= 1000000 ; valoare++) 
    {
        if (!numar_factori[valoare]) {
            for (int multiplu = valoare ; multiplu <= 1000000 ; multiplu += valoare) {
                numar_factori[multiplu]++;
            }
        }

        optiuni[numar_factori[valoare]].push_back(valoare);
    }

    int numar_intrebari;
    for (cin >> numar_intrebari ; numar_intrebari-- ; )
    {
        int limita , indice;
        cin >> limita >> indice;

        if (optiuni[indice].front() > limita)
            { cout << "0\n"; continue; }

        int pozitie = 0;
        for (int putere = 262144 ; putere ; putere >>= 1) {
            if (putere + pozitie < (int)optiuni[indice].size() && optiuni[indice][putere + pozitie] <= limita) {
                pozitie += putere;
            }
        }

        cout << optiuni[indice][pozitie] << '\n';
    }

    cout.close(); cin.close();
    return 0;
}