// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ordered_set = tree<T, null_type,
                         less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = 1e18;
const int mod = 1000000007;
const double eps = 1e-9;
const int N = 600005;

int mdiv[N], nxtp[N], prevp[N], mark[N];
vector<int> primes;

void preprocess() {
    for(int i=1; i<N; i++) 
        for(int j=i*2; j<N; j+=i)
            mdiv[j] = i;

    mark[0] = mark[1] = 1;
    for(int i=2; i<N; i++) {
        if(mark[i]) continue;
        primes.push_back(i);
        for(int j=i*i; j<N; j+=i)
            mark[j] = 1;
    }

    for(int i=0; i<primes.size()-1; i++) {
        nxtp[primes[i]] = primes[i+1];
        prevp[primes[i+1]] = primes[i];
    }

    prevp[2] = -inf;
    nxtp[primes.back()] = inf;
}

int dist[N][2], vis[N][2];

void solve(int tc) {
    int n, m, k;
    cin >> n >> m >> k;

    vis[n][0] = tc;
    dist[n][0] = 0;
    queue<pii> q;
    q.push({n, 0});

    int ans = 0;
    while(!q.empty()) {
        auto [u, p] = q.front();
        q.pop();
        if(dist[u][p] == k) break;

        for(int d=1; d<=m; d++) {
            bool f = 0;
            for(int j=0; j<2; j++) {
                int i = u + d * (j ? 1 : -1);
                if(i == u or i < 2) continue;

                int nxt = i / mdiv[i];

                if(vis[nxt][!p] != tc) {
                    vis[nxt][!p] = tc;
                    dist[nxt][!p] = dist[u][p] + 1;
                    q.push({nxt, !p});
                }
                f |= (!mark[nxt]);
            }
            if(f) break;
        }
    }

    for(int i=2; i<N; i++) {
        if(mark[i]) continue;
        for(int j=0; j<2; j++) {
            if(vis[i][j] != tc) continue;
            int left = k - dist[i][j];
            // cout << i << ' ' << j << ' ' << left << endl;
            if(nxtp[i] - i <= m) {
                if(left % 2) ans = max(ans, nxtp[i]);
                else ans = max(ans, i);

                if(nxtp[nxtp[i]] - nxtp[i] <= m) {
                    if(left % 2 == 0)
                        ans = max(ans, nxtp[nxtp[i]]);
                }
            }
            if(i - prevp[i] <= m) {
                if(left % 2) ans = max(ans, prevp[i]);
                else ans = max(ans, i);
            }
        }
    }

    cout << ans << endl;
}
     
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess(); 

    int T = 1;
    cin >> T;

    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    return 0;
}