#include<bits/stdc++.h>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int NMAX = 1e6;
vector < int > ndp(NMAX + 1);

void Eratostene() {
    for(int i = 2; i <= NMAX; ++i)
        if(ndp[i] == 0)
            for(int j = i; j <= NMAX; j += i)
                ++ndp[j];
}

int main() {
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    Eratostene();
    int Q;
    fin >> Q;
    vector < vector < int > > sol(NMAX + 1, vector < int >(8));
    for(int i = 1; i <= NMAX; ++i) {
        for(int j = 0; j <= 7; ++j)
            sol[i][j] = sol[i - 1][j];
        sol[i][ndp[i]] = i;
    }
    while(Q--) {
        int N, K;
        fin >> N >> K;
        fout << sol[N][K] << '\n';
    }
}