//SUST_ZadeedBoss_Fanclub
//code_korlei_life_ase
//na_korle_lifeNai

#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T> using o_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define double long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
int last = 0;
int mx = 0;
const int N = 500000;
int spf[N];
int sz;
bool prime[N];
vector <int> primes;
void sieve()
{
	for (int i=2; i<N; i++)
	{
		if (spf[i] == 0) {spf[i] = i; prime[i] = 1; sz++; primes.push_back(i);}
		for (int j=0; j<sz && i * primes[j] < N && primes[j] <= spf[i]; j++)
		{
			spf[i * primes[j]] = primes[j];
		}
	}
}

int brute (int n, int m, int k)
{

	if (k == 0) return n;
	if (k == 1)
	{
		return n + m;
	}
	int ans = 0;
	for (int j=-m; j<=m; j++)
	{
		if (n+j<2) continue;
		if (j == 0) continue;
		if (n+j == spf[n+j]) ans = max(ans, brute(n+j, m, k%2));
		else ans = max(ans, brute(spf[n+j], m, k-2));
	}
	return ans;
}
void solve ()
{

	int n, m, k; cin >>n >>m >>k;
	int j = lower_bound(all(primes), n) - primes.begin();
	int h = j - 1;
	int mx = -1;
	if (h >= 0 && n - primes[h] <= m && prime[n] && k%2==0) mx = max(mx, n);
	if (h >= 0 && n - primes[h] <= m && prime[n] && k%2==1) mx = max(mx, primes[h]);
	if (h >= 0 && n - primes[h] <= m && k==1)  mx = max(mx, primes[h]);
	
	if (prime[n]) j++;
	if (primes[j] - n <= m && k%2==0 && prime[n]) mx = max(mx, n);
	if (primes[j] - n <= m && k==1)  mx = max(mx, primes[j]);
	if (primes[j] - n <= m && k%2==1 && prime[n])  mx = max(mx, primes[j]);

	if (primes[j] - primes[j-1] <= m && k%2==0) mx = max(mx, primes[j-1]);

	for (int i=j; i<sz && i-j+1<=k; i++)
	{
		if (primes[i] - (primes[i-1]) <= m)
		{
			if ((i-j+1)%2 == k%2) mx = max(mx, primes[i]);
		}
		else break;
	}



	if (mx == -1)
	{
		mx = brute(n, m, k);
	}
	cout <<mx <<"\n";
}

signed main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	sieve();
	int TCASE = 1;
	cin >> TCASE;

	for (int tcase = 1; tcase <= TCASE; tcase++)
	{
		// cout <<"Case #" <<tcase <<": ";
		solve();
	}

}