#include <bits/stdc++.h>
using namespace std;
const long long BIG = 1e10;
const long long MAX = 1e6 + 10;
long long par[MAX];
long long CNT(long long p, long long x) {
  vector<long long> v;
  v.clear();
  while (p > 1) {
    long long pr = par[p];
    v.push_back(pr);
    while (p % pr == 0) p /= pr;
  }
  long long ans = 0;
  for (int i = 0; i < (1 << (v).size()); i++) {
    long long zarb = 1;
    bool parity = 0;
    for (int j = 0; j < (v).size(); j++) {
      zarb *= (((i >> j) & 1) ? v[j] : 1);
      parity ^= ((i >> j) & 1);
    }
    ans += (parity ? -1 : 1) * (x / zarb);
  }
  return ans;
}
long long solve(long long p, long long k) {
  long long l = 1, r = BIG, ans;
  while (l <= r) {
    long long mid = (l + r) / 2;
    if (CNT(p, mid) <= k - 1) {
      l = mid + 1;
      ans = mid;
    } else {
      r = mid - 1;
    }
  }
  return ans + 1;
}
void prep() {
  for (long long i = 2; i < MAX; i++)
    if (par[i] == 0)
      for (long long j = i; j < MAX; j += i) par[j] = i;
}
int main() {
  prep();
  long long q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    long long x, p, k;
    cin >> x >> p >> k;
    cout << solve(p, k + CNT(p, x)) << endl;
  }
}
