#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 + 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, nn, m;

int dp[10000000][3];
int vis[10000000][3];
int rec(int n, int move)
{

    if (move == k + 1)
        return n;

    if (vis[n][move % 2] == 1)
        return dp[n][move % 2];

    vis[n][move % 2] = 1;

    int ans = 0;
    int p1 = (move % 2 == 1 ? 0 : 1e9);

    if (move % 2)
    {
        for (int j = 1; j <= m; j++)
        {
            p1 = max(p1, rec(n + j, move + 1));
            if (n - j >= 2)
            {
                p1 = max(p1, rec(n - j, move + 1));
            }
        }
    }
    else
    {

        p1 = min(p1, rec((spf[n] == 1 ? n : spf[n]), move + 1));
    }
    // cout << p1 << " " << move  << endll;
    return dp[n][move % 2] = p1;
}

void solve()
{

    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof dp);
    cin >> nn >> m >> k;
    k *= 2;
    cout << rec(nn, 1) << endll;
}

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