#include <bits/stdc++.h>
using namespace std;
long long spf[10000005];
void precomp() {
  for (int i = 0; i < 10000005; i++) {
    spf[i] = LLONG_MAX;
  }
  for (int i = 2; i < 10000005; i++) {
    if (spf[i] != LLONG_MAX) continue;
    for (int j = i; j < 10000005; j += i) {
      if (spf[j] != LLONG_MAX) continue;
      spf[j] = i;
    }
  }
}
long long getAns(long long x, vector<long long> kfac) {
  long long ans = 0;
  long long maxMask = 1 << (kfac.size());
  for (int mask = 1; mask < maxMask; mask++) {
    long long num = 1;
    long long maskCopy = mask;
    long long zz = 0;
    while (maskCopy) {
      if (maskCopy & 1) {
        num *= kfac[zz];
      }
      zz++;
      maskCopy >>= 1;
    }
    long long count = x / num;
    if (__builtin_popcount(mask) & 1) {
      ans += count;
    } else {
      ans -= count;
    }
  }
  return x - ans - 1;
}
vector<long long> getFac(long long k) {
  vector<long long> ans;
  while (k > 1) {
    long long s = spf[k];
    if (ans.size() == 0 || ans[ans.size() - 1] != s) ans.push_back(s);
    k /= s;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  precomp();
  long long t;
  cin >> t;
  while (t--) {
    long long x, p, k;
    cin >> x >> p >> k;
    vector<long long> fac = getFac(p);
    long long countAns = getAns(x, fac);
    long long target = countAns + k;
    long long bmin = x;
    long long bmax = 10000005 - 1;
    while (bmin < bmax) {
      long long bmid = (bmin + bmax) / 2;
      long long midAns = getAns(bmid, fac);
      if (midAns < target) {
        bmin = bmid + 1;
      } else {
        bmax = bmid;
      }
    }
    cout << bmin << endl;
  }
}
