#include <cstdio>
#include <fstream>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <bitset>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <cstring>


#define ll long long
#define llu unsigned long long
#define rep(i, a, b) for (int i = (a) ; i <= (b) ; ++i)

#define mp make_pair
#define pii pair <int, int>
#define SORT(x) sort ((x).begin(), (x).end() )
#define fi first

const int QMAX = 1000001;

int viz[QMAX], sol[QMAX][8];

using namespace std;

inline void ciuruiala(){
    for (int i = 2 ; i <= QMAX; i ++) {
            if (viz[i] == 0) {
                for (int j = i ; j <= QMAX; j += i)
                ++viz[j];
            }
    }
}
inline int bitsearch (int x, int k){
    int st, dr, mid, last = 1 ;
    st = 1, dr = sol[800][k];
    while (st <= dr) {
            mid = st + ((dr-st)>>1);
    if (sol[mid][k] > x) dr = mid - 1;
    else st = mid + 1, last = sol[mid][k];
    }
    return (last == 1 ? 0 : last);
}

int main(){
    ifstream fin ("divprim.in");
    ofstream fout ("divprim.out");
    int teste, X, queryType;
    ciuruiala();
    for (int i = 2 ; i <= QMAX; ++i)
        if (viz[i] < 8) sol[++sol[viz[i]][0]][viz[i]] = i;
        // sol[i][j] al J-lea nr cu i divizori
        for (fin >> teste; teste; teste--){
                fin >> X >> queryType;
        fout << bitsearch(X,queryType) << "\n";
        }
        return 0;


}