#include <bits/stdc++.h>
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set1;
typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set2;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_s;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_s2;
typedef long long int ll;
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
const int N = 1200300;
#define pi 2 * acos(0.0)
#define vll vector<ll>
#define pq_ priority_queue
#define pq_min <int,vector<int>,greater<int>>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pb push_back
#define sp ' '
#define sz(n) (int)n.size()
#define all(n) n.begin(), n.end()
#define rall(n) n.rbegin(), n.rend()
#define YES cout << "YES\n";
#define yes cout << "yes\n";
#define NO cout << "NO\n";
#define no cout << "no\n";
#define bye return 0;
#define ss second;
#define ff first;
const double eps = 1e-9;
const int MAX = 1e5;
const int lim = 1e6;
bool odd(ll num) { return ((num & 1) == 1); }
bool even(ll num) { return ((num & 1) == 0); }
bool isEqual(double a, double b) { return abs(a - b) < eps; }
bool isGreater(double a, double b) { return a >= b + eps; }
bool isGreaterEqual(double a, double b) { return a > b - eps; }
#define tc \
int tt; \
cin >> tt; \
while (tt--)
#define mset(n, v) memset(n, v, sizeof(n))
#define chk(n) for (auto it : n)
#define ff1(i, n) for (int i = 1; i <= n; i++)
#define lcm(a, b) (((a) * (b)) / __gcd(a, b))
int dx[8] = {1, -1, 0, 0, 1, -1, -1, 1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
ll mn(ll x, ll y)
{
if (x < y)
return x;
else
return y;
}
ll maxx(ll x, ll y)
{
if (x > y)
return x;
else
return y;
}
string bin(int n)
{
std::string binary;
while (n > 0)
{
ll x=n%2;
char y = x+'0';
binary+=y;
n /= 2;
}
// Reverse the vector to get the binary representation in correct order
std::reverse(binary.begin(), binary.end());
return binary;
}
ll POW(ll a, ll b)
{
if (!b)
return 1;
ll r = POW(a, b / 2);
if (b % 2)
return r * r * a;
else
return r * r;
}
void pri(vi v)
{
for (auto it : v)
cout << it << ' ';
cout << endl;
}
void pri1(vi v)
{
for (auto it : v)
cout << it << ' ';
}
void pro(vll v)
{
for (auto it : v)
cout << it << ' ';
cout << endl;
}
int mex(vi v, int l, int r)
{
vi a;
for (int i = l; i <= r; i++)
{
a.pb(v[i]);
}
sort(all(a));
for (int i = 0, j = 1; i < a.size(); i++)
{
if (a[i] == j)
{
j++;
}
else
{
return j;
}
}
return a.back() + 1;
}
vector<int> cps(const vector<int> &arr)
{
int n = arr.size();
vector<int> prefixSum(n);
if (n > 0)
{
prefixSum[0] = arr[0];
for (int i = 1; i < n; ++i)
{
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
}
return prefixSum;
}
bool comp(pair<int, int> x, pair<int, int> y)
{
if (x.second > y.second)
return true;
else if (x.second == y.second)
{
if (x.first > y.first)
return true;
else
return false;
}
else
return false;
}
bool comp1(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y)
{
if (x.first > y.first)
return true;
else if (x.first == y.first)
{
if (x.second.second < y.second.second)
return true;
else
return false;
}
else
return false;
}
bool comp2(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y)
{
if (x.second.first > y.second.first)
return true;
else if (x.second.first == y.second.first)
{
if (x.second.second < y.second.second)
return true;
else
return false;
}
else
return false;
}
ll PoW(ll base, ll exponent)
{
ll result = 1;
for (int i = 0; i < exponent; ++i)
{
result = (result * base) % 10;
;
}
return result;
}
bool isp(ll num)
{
ll om = num;
ll rm = 0;
while (num > 0)
{
ll digit = num % 10;
rm = rm * 10 + digit;
num /= 10;
}
return om == rm;
}
string lcs(const std::vector<std::string> &strs)
{
std::vector<std::string::const_reverse_iterator> backs;
std::string s;
if (strs.size() == 0)
return "";
if (strs.size() == 1)
return strs[0];
for (auto &str : strs)
backs.push_back(str.crbegin());
while (backs[0] != strs[0].crend())
{
char ch = *backs[0]++;
for (std::size_t i = 1; i < strs.size(); i++)
{
if (backs[i] == strs[i].crend())
goto done;
if (*backs[i] != ch)
goto done;
backs[i]++;
}
s.push_back(ch);
}
done:
reverse(s.begin(), s.end());
return s;
}
bool leap(int year)
{
return (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0));
}
bool isd(string s, ll d, ll y)
{
if (d == 32)
return 0;
if (s == "April" || s == "June" || s == "September" || s == "November")
{
if (d == 31)
return 0;
return 1;
}
if (d > 28 && s == "February")
{
if (d == 29 && leap(y))
{
return 1;
}
return 0;
}
return 1;
}
vll pref(vll v)
{
vll pr;
pr.pb(v.front());
for (int i = 1; i < v.size(); i++)
{
pr.pb(v[i] + pr[i - 1]);
}
return pr;
}
ll cxor(vi v, ll l, ll r)
{
ll xo = v[l];
for (int i = l + 1; i <= r; i++)
{
xo ^= v[i];
}
return xo;
}
#define seea(a, x, y) \
for (int i = x; i < y; i++) \
{ \
cin >> a[i]; \
}
#define seev(v, n) \
for (int i = 0; i < n; i++) \
{ \
int x; \
cin >> x; \
v.push_back(x); \
}
#define sees(s, n) \
for (int i = 0; i < n; i++) \
{ \
int x; \
cin >> x; \
s.insert(x); \
}
bool is(int num, int pos)
{
// Create a mask with only the i'th bit set
int mask = 1 << pos;
// Perform bitwise AND operation to isolate the i'th bit
int result = num & mask;
// Check if the result is non-zero (bit is set)
return result != 0;
}
// By Nitin Patel
// Function to merge two sorted subarrays of a given array
void merge(long long start, long long end,
vector<long long> &prefix)
{
long long n = end - start + 1;
long long mid = (start + end) / 2;
vector<long long> temp(n, 0);
long long i = start;
long long j = mid + 1;
long long k = 0;
// Merge the two subarrays in sorted order
while (i <= mid and j <= end)
{
if (prefix[i] <= prefix[j])
{
temp[k++] = prefix[i++];
}
else
{
temp[k++] = prefix[j++];
}
}
// Copy the remaining elements of the left subarray, if
// any
while (i <= mid)
{
temp[k++] = prefix[i++];
}
// Copy the remaining elements of the right subarray, if
// any
while (j <= end)
{
temp[k++] = prefix[j++];
}
// Copy the merged subarray back to the original array
for (int t = start; t <= end; t++)
{
prefix[t] = temp[t - start];
}
}
bool isvo(char x)
{
if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u')
return 1;
return 0;
}
bool is_prime(ll x)
{
for (ll i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
return 0;
}
}
return 1;
}
bool cm(pair<char, pair<int, int>> x, pair<char, pair<int, int>> y)
{
if (x.second.first == y.second.first)
{
if (x.second.second > y.second.second)
{
return 1;
}
return 0;
}
else
{
return x.second.first < y.second.first;
}
}
vll sieve(ll n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime numbers.
for (ll i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (ll j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
ll cn=0;
vll primes;
for (ll i = 2; i <= n; i++) {
if (is_prime[i]) {
if(i<=n*n)
primes.pb(i);
}
}
return primes;
}
bool cc(pair<vi,int> xx,pair<vi,int> yy){
ll cn=0;;
vi x=xx.first, y=yy.first;
for(int i=0;i<5;i++){
if(x[i] <y[i]){
cn++;
}
}
return cn>5-cn;
}
int main()
{
tc{
ll n, m, k;
cin>>n>>m>>k;
ll ans=0;
for(int i=n+m*k;i>=max(n-m*k, 2ll);i--){
ll f=0;
for(int j=2;j*j<=i;j++){
if(i%j==0){
f=1;
break;
}
}
if(!f){
ans=max(ans, i*1ll);
break;
}
}
ll an1=0;
for(int i=n+m*k;i>=max(n-m*k, 2ll);i--){
ll f=0;
if(i==ans) continue;
for(int j=2;j*j<=i;j++){
if(i%j==0){
f=1;
break;
}
}
if(!f){
an1=max(an1, i*1ll);
break;
}
}
if(k%2==1 || an1==n){
ans=an1;
}
cout<<ans<<endl;
}
}