//SUST_life_nai
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long
#define f(i,s,n) for(int i = s; i < n; i++)
int sz = 1e7;
vector<int> prm(sz + 5, 1), spf(sz + 5, 0), minpr(sz+1,1e10);

void prec(){
    spf[0] = -1, spf[1] = -1;
    prm[1] = 0;
    int lastorime = 0;
    for(int i = 2; i <= sz; i++){
        spf[i] = i;
        minpr[i] = i;
    }
    for(int i = 2; i <= sz; i++){
        if(spf[i] != i)continue;
        // if(i - lastorime > 100) cout << i << " " << lastorime << nl;
        for(int j = i * i; j <= sz; j += i){
            if(spf[j] == j) minpr[j] = i; 
            spf[j] = i;
            prm[j] = 0;

        }
        lastorime = i;
    }
}

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

    auto updPos = [&](int val){
        int jabo = -1;
        for(int i = val + 1; i <= val + m; i++){
            if(prm[i])jabo = i;
        }
        return jabo;
    };

    auto updNeg = [&](int val){
        int jabo = -1;
        for(int i = val - 1; i >= max(val - m, 2LL); i--){
            if(prm[i]){jabo = i;break;}
        }
        return jabo;
    };

    while(k){
        int jabo = updPos(n);
        if(jabo == -1){
            jabo = updNeg(n);
            int tmpPos = 2;
            for(int i = n + 1LL; i <= n + m; i++){  
                tmpPos = max(minpr[i],tmpPos);
                // cout<<i<<" "<<tmpPos<<nl;
            }
            if(jabo == -1 || tmpPos >= jabo){
                int tem = 2;
                for(int i = n + 1LL; i <= n + m; i++){  
                    tem = max(minpr[i],tem);
                }
                for(int i = n - 1LL; i >= max(n - m, 2LL); i--){
                   tem = max(minpr[i],tem);
                }
                if(n == tem){cout<<n<<nl;return;}
                n = tem;
            }
            else{
                if(k % 2LL){
                    if(k != 1LL) {
                        int tem = 2;
                        for(int i = n - 1LL; i >= max(n - m, 2LL); i--){
                            tem = max(minpr[i],tem);
                        }
                        if(tem + m >= jabo)jabo = n;
                    }
                    cout<<jabo<<nl;
                }
                else cout<<n<<nl;   
                return;
            }
        }
        else n = jabo;
        k--;
    }
    cout<<n<<nl;
}

signed main() {
   ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   int T = 1;
   cin>>T;
    prec();
    // for(int i = 1; i <= 100; i++) cout << minpr[i] << nl;
    // for(int i = 1300; i <= 1600; i++)if(prm[i])cout<<i<<nl;
   for(int tc = 1; tc <= T; tc++){
        solve();
        // cout<<"a"<<nl;
   }
}