#include<bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<"\n";
#define no cout<<"NO"<<"\n";
#define forn  for(int i=0;i<n;i++);
#define acin  for(int i=0;i<n;i++)cin>>arr[i];
#define v vector<int>arr(n);
#define int long long
const int mx=123;
bool isprime[mx];
vector<int>prime;
void solve()
{
  int n, m, k;
  cin >> n >> m >> k; // k-x,x1,x2;
 if(m==1){cout<<n<<endl;return;}

  int p = 1;
  while (k--)
  {
      //if(p>m)break;
    if (n - p >= 2)
      n -= p;
    else
    {
      n += p;
      if (n % 2 == 0)
      {
        int c = n / 2;
        n = n / c;
      }
      else
      {

        if (isprime[n])
          n = n;
        else
        {
          int c = n / 2;
          for (int i = c; i >= 1; i--)
          {
            if (n % i == 0)
            {
              n /= i;
            }
          }
        }
      }
    }
    p++;
  }
 cout<<n<<endl;
}

int32_t main()
{
  for (int i = 3; i <= mx; i += 2)
    isprime[i] = 1;
  for (int i = 3; i <= sqrt(mx); i++)
  {
    if (isprime[i])
    {
      for (int j = i * i; j <= mx; j += i)
      {
        isprime[j] = 0;
      }
    }
  }
  isprime[2] = 1;
  prime.push_back(2);
  for (int i = 3; i <= mx; i += 2)
  {
    if (isprime[i] == 1)
      prime.push_back(i);
  }
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }
}