#include <bits/stdc++.h>
using namespace std;
long long int f(long long int pos, long long int p) {
  vector<long long int> factors;
  for (long long int i = 2; i * i <= p; i++)
    if (p % i == 0) {
      factors.push_back(i);
      while (p % i == 0) p /= i;
    }
  if (p > 1) factors.push_back(p);
  int sz = ((int)(factors).size());
  long long int ans = 0;
  for (int mask = 0; mask < (1 << sz); mask++) {
    long long int num = 1;
    for (int i = 0; i < sz; i++)
      if ((mask >> i) & 1) num *= factors[i];
    int sign = (__builtin_popcountll(mask) & 1) ? -1 : +1;
    ans += sign * pos / num;
  }
  return ans;
}
void solve(void) {
  int x, k, p;
  cin >> x >> p >> k;
  if (p == 1) {
    cout << x + k << '\n';
    return;
  }
  k += f(x, p);
  long long int fp = f(p, p);
  long long int lo = -1, hi = p - 1;
  while (hi - lo > 1) {
    long long int mid = (lo + hi) >> 1;
    if (f(mid, p) >= (k % fp == 0 ? fp : k % fp))
      hi = mid;
    else
      lo = mid;
  }
  cout << hi + 1LL * p * ((k - 1) / fp) << '\n';
}
int main() {
  int q;
  cin >> q;
  while (q--) solve();
  return 0;
}
