#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 1000000
using namespace std;

int nr_divs[NMAX + 5];
int m[8][NMAX + 5];
int nr[8];

void make_sleve(){
    m[0][++nr[0]] = 1;

    for (int i = 2; i <= NMAX; ++i){

        if (!nr_divs[i]){

            //if (i <= 1000)
            for (int j = i; j <= NMAX; j += i)
                ++nr_divs[j];
        }
        m[nr_divs[i]][++nr[nr_divs[i]]] = i;
    }
}

int main()
{
    #define USE_FILES
    #ifdef USE_FILES
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");

    #define cin fin
    #define cout fout
    #endif // USE_FILES

    make_sleve();

    int t;
    cin >> t;

    for (int i = 0; i < t; ++i){
        int n, k;
        cin >> n >> k;

        int st = 0;
        int dr = nr[k];

        while (st <= dr){
            int mij = (st + dr) / 2;
            if (m[k][mij] > n){
                dr = mij - 1;
            }
            else st = mij + 1;
        }

        cout << m[k][dr] << '\n';
    }


    return 0;
}