#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 = 1e7 + 9999 + 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 * 2; 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 mx = -1;
    int rem = -1;
    int ok = 0;
    for (int i = 1; i <= k; i++)
    {
        int prm = -1, non_prm = -1, node = -1;
        vector<int> v;
        for (int j = 1; j <= m; j++)
        {
            if (spf[n + j] == n + j)
            {
                prm = max(prm, n + j);
                v.pb(n + j);
            }
            else
            {

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

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

                    prm = max(prm, spf[n - j]);
                    v.pb(spf[n - j]);
                }
            }
        }
        n = prm;
        sort(all(v));
        for (auto j : v)
        {
            // cout << j<< " = " << prm << endll;
            if (j != prm)
            {
                if (j + m >= prm)
                {
                    ok = 1;
                }
            }
        }
        // cout << n << endll;
        mx = max(mx, n);
        // cout << i << " = " << n << endll;
        if (mp[n])
        {

            // cout << "PAichi at = " << mp[n] << endll; ;
            // cout << n << " " << k - i << endll;
            rem = k - i;
            break;
            // ;
        }
        prev = n;
        mp[n] = i;
    }

    if (ok)
    {
        cout << mx << endll;
    }
    else
    {
        cout << n << endll;
    }

    // if (rem != -1)
    // {
    // }
    // else
    //     cout << n << endll;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    sp();
    // for (int i = 1; i <= 100; i++)
    // {
    //     cout << spf[i] << " ";
    // }
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}