#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];
            }
    }
}
int main(){
    ifstream fin ("divprim.in");
    ofstream fout ("divprim.out");
    int teste, X, queryType;
    ciuruiala();
    for (int i = 1 ; i <= QMAX; i++)
        for (int j = 1; j <= 7; ++j)
        sol[i][j] = sol[i-1][j], sol[i][viz[i]] = i;

    for (fin >> teste; teste; teste--){
            fin >> X >> queryType;
    fout << sol[X][queryType] << "\n";
    }
        return 0;


}