#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;

    queue<pair<int, int>> q;
    q.push({n, k});
    map<pair<int, int>, int> vis;
    int ans = 0;
    // vis[spf[n]]++

    while (q.size())
    {
        auto p = q.front();
        q.pop();
        for (int i = 1; i <= m; i++)
        {
            int samne = p.first + i;
            int pichone = p.first - i;

            samne = spf[samne];

            if (p.second == 0)
            {
                ans = max(ans, p.first);
                break;
            }

            // if (vis[samne] && abs((p.first + i) - samne) <= m && p.second % 2 == 0)
            // {
            //     ans = max(ans, samne);
            // }
            // else

            {

                int starting = spf[p.first], ending = spf[p.first + i];
                // cout << starting << " " << ending << endll;

                if (vis[{samne, samne}])
                {
                    if (p.second % 2)
                    {
                        ans = max(ans, ending);
                    }
                    else
                        ans = max(ans, starting);
                }
                else
                {

                    q.push({samne, p.second - 1});
                    vis[{samne, samne}] = p.second - 1;
                }
            }

            if (pichone >= 2)
            {
                pichone = spf[pichone];
                int starting = spf[p.first], ending = spf[p.first - i];
                // cout << starting << " " << ending << endll;
                ;

                if (vis[{pichone, pichone}])
                {
                    if (p.second % 2)
                    {
                        ans = max(ans, ending);
                    }
                    else
                        ans = max(ans, starting);
                }
                else
                {

                    q.push({pichone, p.second - 1});
                    vis[{pichone, pichone}] = p.second - 1;
                }
            }
            // cout << endll;
            // cout << ans << endll;
            // cout << samne << " " << pichone << endll;
        }
        // cout << endll;
    }
    cout << ans << 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;
}