#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const int INF = 1e9;
const long long mod = 1e9 + 7;
const double Pi = acos(-1);
void Fastio() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n, m;
int BIT[200005];
void Update(int node, int val) {
  for (node; node <= m; node += node & -node) {
    BIT[node] += val;
  }
}
int Get(int node) {
  int ans = 0;
  for (node; node > 0; node -= node & -node) {
    ans += BIT[node];
  }
  return ans;
}
int t;
int x, p, k;
int Seive[1000005], dp[128], c[128], H[128];
int f(int x, vector<int> Prime) {
  dp[0] = 1;
  int ans = 0;
  for (int i = 1; i < 1 << Prime.size(); i++) {
    dp[i] = dp[i ^ (1 << H[i])] * Prime[H[i]];
    if (c[i] & 1) {
      ans += (x / dp[i]);
    } else {
      ans -= (x / dp[i]);
    }
  }
  return x - ans;
}
signed main() {
  Fastio();
  cin >> t;
  for (int i = 2; i <= 1000; i++) {
    if (!Seive[i]) {
      Seive[i] = i;
      for (int j = i * i; j <= 1000000; j = j + i) {
        Seive[j] = i;
      }
    }
  }
  for (int i = 1; i <= 1000000; i++) {
    if (Seive[i] == 0) {
      Seive[i] = i;
    }
  }
  H[0] = -2;
  for (int i = 0; i <= 127; i++) {
    c[i] = c[i >> 1] + (i & 1);
    H[i] = H[i >> 1] + 1;
  }
  while (t--) {
    cin >> x >> p >> k;
    vector<int> Prime;
    while (p > 1) {
      Prime.emplace_back(Seive[p]);
      while (p % Prime.back() == 0) {
        p /= Prime.back();
      }
    }
    int temp = f(x, Prime) + k;
    int l = 1, r = 2e9;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (f(mid, Prime) >= temp) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    cout << l << '\n';
  }
}
