#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

int dp[1000001][8];
int cnt[1000001];

void sieve() {
    for(int i = 2;i <= 1000000;i++)
        if(cnt[i] == 0) {
            for(int j = i;j <= 1000000;j += i)
                cnt[j]++;
        }

    for(int i = 2;i <= 1000000;i++) {
        for(int k = 1;k <= 7;k++)
            dp[i][k] = dp[i - 1][k];
        dp[i][cnt[i]] = i;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("divprim");

    sieve();

    int T; cin >> T;

    while(T--) {
        int N, K; cin >> N >> K;
        cout << dp[N][K] << "\n";
    }

    return 0;
}