#include <fstream>
using namespace std;

int T;

pair<int, int> Q[100001];
int dp[1000001][8];
int Maxa, Maxb;

void read() {
    int i;
    ifstream f("divprim.in");
    f >> T;
    for (i = 1; i <= T; i++) {
        f >> Q[i].first >> Q[i].second;
        if (Q[i].first > Maxa)
            Maxa = Q[i].first;
        if (Q[i].second > Maxb)
            Maxb = Q[i].second;
    }
    f.close();
}

int nr[1000001];

void Ciur() {
    int i, j;
    nr[0] = nr[1] = 1;
    for (i = 2; i <= 1000000; i++)
        if (!nr[i])
            for (j = 1; j * i <= 1000000; j++) 
                nr[i * j]++;

}

void solve() {
    int i, d, k, x, j;
    Ciur();
    for (i = 1; i <= Maxa; i++) {
        for (j = 0; j <= Maxb; j++)
            dp[i][j] = dp[i - 1][j];
        dp[i][nr[i]] = i;
    }
}

void output() {
    int i;
    ofstream g("divprim.out");
    for (i = 1; i <= T; i++)
        g << dp[Q[i].first][Q[i].second] << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}