#include<bits/stdc++.h>
#define ll long long int
using namespace std;
vector<ll>v;
ll mxn=5e6+7;
bool mp[10000007];
void seive(){
  for(ll i=2;i<=mxn;i++){
    if(mp[i]==0){
      v.push_back(i);
      for(ll j=i+i;j<=mxn;j+=i){
        mp[j]=1;
      }
    }
  }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc=1,tc1=1;
    cin>>tc;
    seive();
    up:
    while(tc--){
      ll n,m,k,ans=2;
      cin>>n>>m>>k;
      for(ll i=max(2LL,n-m);i<=n+m;i++){
        if(i==n){
          continue;
        }
        if(mp[i]==0){
          ans=i;
        }
      }
      if(ans==2){
        for(ll i=max(2LL,n-m);i<=n+m;i++){
          if(i==n){
            continue;
          }
          for(ll j=2;j*j<=i;j++){
            if(i%j==0){
              ans=max(ans,j);
              break;
            }
          }
        }
      }
      k--;
      ll op,ty=1;
      for(ll cnt=1;cnt<=k;cnt++){
        ll lo=0,hi=v.size()-1,here=ans;
        while(lo<=hi){
          ll mid=(lo+hi)>>1LL;
          if(ans+m>=v[mid]){
            here=v[mid];
            lo=mid+1;
          }
          else {
            hi=mid-1;
          }
        }
        if(here==ans){
          ty=0;
          break;
        }
        else {
          ans=here;
        }
      }
      if(ans==2){
        op=3;
      }
      else {
        for(ll i=ans-1;i>=2;i--){
          if(mp[i]==0){
            op=i;
            break;
          }
        }
      }
      if(ty==1){
        cout<<ans<<'\n';
        goto up;
      }
      if(k%2==0){
        cout<<ans<<'\n';
      }
      else {
        cout<<op<<'\n';
      }
    }
}