Problem Setter: Kamonasish Roy (Bullet)
Problem tag: Number theory, Game theory, Shortest path, BFS,DFS.
Tutorial :
1st observation : Roy always tries to travel between prime numbers. Because a prime number has the largest divisor, which is 1, except for its own number. In this case, Hridoy can’t back him up.
2nd observation : Once Roy reached the largest prime number, he can’t move to the next largest prime number, where the next largest prime number distance is greater than m. Now, he can fill up with remaining moves a previous prime number with a distance less than or equal to m. If the remaining moves are an even number, he can always stay in this position; otherwise, he must go to his previous prime number. So we need to calculate each prime position, one for minimum even number moves and the other for minimum odd number moves.
3rd observation : We can use the BFS method to calculate the source position to each possible prime position where Roy can travel, one for minimum even number moves to reach this position and the other one for minimum odd number moves.
When we move from one position to another, just consider the prime numbers. Since m is at most 100, we can reach up to 370261. After that prime difference is more than 100, so we can’t go any higher prime.

Let, X = total prime number between 2 to 370261 = 31545.
Time Complexity: O( (X + X) * m ).

Author code :

#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;
 
}

Tester Code (Sajid Zakaria) :

// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// #define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ordered_set = tree<T, null_type,
                         less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = 1e9;
const int mod = 1000000007;
const double eps = 1e-9;
const int N = 400005;

int mdiv[N], nxtp[N], prevp[N], mark[N];
vector<int> primes;

void preprocess() {
    for(int i=1; i<N; i++) 
        for(int j=i*2; j<N; j+=i)
            mdiv[j] = i;

    mark[0] = mark[1] = 1;
    for(int i=2; i<N; i++) {
        if(mark[i]) continue;
        primes.push_back(i);
        if(1ll * i * i >= N) continue;
        for(int j=i*i; j<N; j+=i)
            mark[j] = 1;
    }

    for(int i=0; i<primes.size()-1; i++) {
        nxtp[primes[i]] = primes[i+1];
        prevp[primes[i+1]] = primes[i];
    }

    prevp[2] = -inf;
    nxtp[primes.back()] = inf;
}

int dist[N][2], vis[N][2];

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

    vis[n][0] = tc;
    dist[n][0] = 0;
    queue<pii> q;
    q.push({n, 0});

    int ans = 0;
    while(!q.empty()) {
        auto [u, p] = q.front();
        q.pop();
        if(dist[u][p] == k) break;

        int primes = 0;
        for(int d=1; d<=m; d++) {
            bool f = 0;
            for(int j=0; j<2; j++) {
                int i = u + d * (j ? 1 : -1);
                if(i == u or i < 2) continue;

                int nxt = i / mdiv[i];

                if(vis[nxt][!p] != tc) {
                    vis[nxt][!p] = tc;
                    dist[nxt][!p] = dist[u][p] + 1;
                    q.push({nxt, !p});
                }
                primes += (!mark[nxt]);
            }
            // if(primes > 4) break;
            // if(f) break;
        }
    }

    for(int i=2; i<N; i++) {
        for(int j=0; j<2; j++) {
            if(vis[i][j] != tc) continue;
            if(dist[i][j] == k) ans = max(ans, i);
            if(mark[i]) continue;
            int left = k - dist[i][j];
            // cout << i << ' ' << j << ' ' << left << endl;
            if(nxtp[i] - i <= m) {
                if(left % 2) ans = max(ans, nxtp[i]);
                else ans = max(ans, i);

                if(left > 1 and nxtp[nxtp[i]] - nxtp[i] <= m) {
                    if(left % 2 == 0)
                        ans = max(ans, nxtp[nxtp[i]]);
                }
            }
            if(i - prevp[i] <= m) {
                if(left % 2) ans = max(ans, prevp[i]);
                else ans = max(ans, i);
            
                if(left > 1 and prevp[i] - prevp[prevp[i]] <= m) {
                    if(left % 2 == 0)
                        ans = max(ans, prevp[prevp[i]]);
                }
            }
        }
    }

    cout << ans << endl;
}
     
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess(); 

    int T = 1;
    cin >> T;

    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    return 0;
}