#include<bits/stdc++.h>
using namespace std;
const long long M=5e5+10,MOD=998244353;
typedef long long ll;
#define debug(x) cout<<x<<endl
int p[M];
int nxt[M];
int pr[M];
int vis[M][2];
void precal(){
for(int i=1;i<M;i++)p[i]=i,nxt[i]=M;
for(int i=2;i<M;i++){
for(int j=i+i;j<M;j+=i)p[j]=j/i;
}
for(int i=2;i<M;i++){
if(p[i]==i)pr[i]=i;
pr[i]=max(pr[i],pr[i-1]);
}
for(int i=M-10;i>=2;i--){
if(p[i]==i)nxt[i]=i;
nxt[i]=min(nxt[i],nxt[i+1]);
}
int cnt=0;
//for(int i=2;i<=3e5;i++)cnt+=(p[i]==i);
//cout<<cnt*2*100*10<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
precal();
int t=1;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({n,k});
int ans=2;
//vis[n][k%2]=1;
while(!pq.empty()){
int cur_n=pq.top().first;
int cur_k=pq.top().second;
//cout<<cur_n<<" "<<cur_k<<endl;
pq.pop();
for(int i=1;i<=m;i++){
int x=cur_n+i;
int y=cur_n-i;
if(cur_k==1){
ans=max(ans,p[x]);
if(y>1)ans=max(ans,p[y]);
}
else{
if(!vis[p[x]][(cur_k-1)%2]){
pq.push({p[x],cur_k-1});
vis[p[x]][(cur_k-1)%2]=1;
}
if(y>1 && !vis[p[y]][(cur_k-1)%2]){
pq.push({p[y],cur_k-1});
vis[p[y]][(cur_k-1)%2]=1;
}
}
}
if(cur_n==p[cur_n]){
int samna=nxt[cur_n+1];
int picha=pr[cur_n-1];
if(samna-cur_n<=m){
if(cur_k & 1)ans=max(samna,ans);
else ans=max(ans,cur_n);
}
if(picha>1 && cur_n-picha<=m){
if(cur_k & 1)ans=max(picha,ans);
else ans=max(ans,cur_n);
}
}
}
cout<<ans<<"\n";
int limit=4e5;
for(int i=2;i<=limit;i++){
vis[i][0]=vis[i][1]=0;
}
}
return 0;
}