#include <bits/stdc++.h>
#define int long long
#define endll '\n';
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int mod = 1e9 + 7, N = 4e5 + 9;

vector<int> prime, spf(N), primeVis(N);
void sp()
{
    for (int i = 1; i < N; i++)
        spf[i] = i;
    for (int p = 2; p < N; p++)
    {
        if (spf[p] == p)
        {
            prime.pb(p);
            primeVis[p] = 1;
            for (int i = p * p; i < N; i += p)
                spf[i] = min(p, spf[i]);
        }
    }
}

int k, n, m;

void solve()
{
    map<int, int> mp;

    int prev = -1;
    // memset(dp, 0, sizeof dp);
    // memset(vis, 0, sizeof dp);
    // cout << endll;
    cin >> n >> m >> k;
    // k *= 2;
    // cout << rec(nn, 1) << endll;
int rem = -1;
    for (int i = 1; i <= k; i++)
    {
        int prm = -1, non_prm = -1, node = -1;
        for (int j = 1; j <= m; j++)
        {
            if (spf[n + j] == n + j)
            {
                prm = max(prm, n + j);
            }
            else
            {

                prm = max(prm, spf[n + j]);
            }

            if (n - j >= 2)
            {
                if (spf[n - j] == n - j)
                {
                    prm = max(prm, n - j);
                }
                else
                {

                    prm = max(prm, spf[n - j]);
                }
            }
        }

        n = prm;
        if (mp[n])
        {
            // cout << n << " " << k - i << endll;
            rem = k - i;
            break;;
        }
        prev = n;
        mp[n]++;
    }


    if(rem != -1) {
        if(rem % 2 == 0) {
            cout << n << endll;
        }
        else {
            cout << prev << endll;
        }
    }
    else cout << n << endll;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    sp();
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}