#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 + 1, 1), spf(sz + 1, 0), minpr(sz+1,1e10);

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

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

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

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

    while(k){
        int jabo = updPos(n);
        if(jabo == -1){
            jabo = updNeg(n);
            if(jabo == -1){
                 int tem = 1;
                for(int i = n + 1; i <= n + m; i++){
                    tem = max(minpr[i],tem);
                }
                for(int i = n - 1; i >= max(n - m, 2LL); i--){
                    tem = max(minpr[i],tem);
                }
                n = tem;
            }
            else{
                if(k % 2)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 = 1300; i <= 1600; i++)if(prm[i])cout<<i<<nl;
   for(int tc = 1; tc <= T; tc++){
        solve();
        // cout<<"a"<<nl;
   }
}