#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 100;
const int MAXP = MAXN + 100;
const int LOGK = 32;

vector<int> spf(MAXP);              // Smallest prime factor
vector<int> primes;                 // All primes up to MAXP
unordered_map<int, int> pIndex;     // prime -> index in primes
vector<vector<int>> dp;            // dp[i][j] = apply f 2^j times to prime i
vector<int> f, g;                   // f[i] = result after one full move, g[i] = Roy-only move result

void sieve(int N) {
    for (int i = 2; i <= N; ++i) {
        if (!spf[i]) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || i * p > N) break;
            spf[i * p] = p;
        }
    }
}

int get_spf(int x) {
    return spf[x];
}

int get_largest_divisor(int x) {
    int res = 1;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            res = max(res, x / i);
            res = max(res, i);
        }
    }
    return res;
}

void precompute(int m) {
    int P = primes.size();
    f.resize(P);
    g.resize(P);
    dp.assign(P, vector<int>(LOGK));

    // Map primes to index
    for (int i = 0; i < P; ++i) {
        pIndex[primes[i]] = i;
    }

    // Precompute f and g for each prime
    for (int i = 0; i < P; ++i) {
        int n = primes[i];
        int best_spf = 0, best_n = n;

        for (int x = 1; x <= m; ++x) {
            for (int sign : {-1, 1}) {
                int new_n = n + sign * x;
                if (new_n >= 2 && new_n < MAXP) {
                    int s = get_spf(new_n);
                    if (s > best_spf) {
                        best_spf = s;
                        best_n = s;
                    }
                }
            }
        }
        f[i] = pIndex[best_n];

        // Roy-only move: just maximize n+x or n−x under constraint
        int max_n = n;
        for (int x = 1; x <= m; ++x) {
            if (n - x >= 2) max_n = max(max_n, n - x);
            max_n = max(max_n, n + x);
        }
        g[i] = max_n;
    }

    // Binary lifting table
    for (int i = 0; i < P; ++i)
        dp[i][0] = f[i];

    for (int j = 1; j < LOGK; ++j)
        for (int i = 0; i < P; ++i)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}

int apply_moves(int n, int m, long long k) {
    // Map n to smallest prime factor
    if (n != spf[n])
        n = spf[n];

    int idx = pIndex[n];
    long long t = k / 2;

    // Apply binary lifting t times
    for (int i = 0; i < LOGK; ++i)
        if (t & (1LL << i))
            idx = dp[idx][i];

    if (k % 2 == 1)
        return g[idx]; // One final Roy-only move
    else
        return primes[idx];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    sieve(MAXP); // Precompute all primes and SPF
    int max_m = 0;
    vector<tuple<int, int, long long>> queries(T);
    for (int i = 0; i < T; ++i) {
        int n, m;
        long long k;
        cin >> n >> m >> k;
        queries[i] = {n, m, k};
        max_m = max(max_m, m);
    }

    precompute(max_m);

    for (auto &[n, m, k] : queries) {
        cout << apply_moves(n, m, k) << '\n';
    }

    return 0;
}