#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
vector<int> primes;
bitset<N> bs;
void sieve() {
  bs.set();
  bs[0] = bs[1] = 0;
  for (long long i = 2; i < N; i++) {
    if (bs[i]) {
      for (long long j = i * i; j < N; j += i) bs[j] = 0;
      primes.push_back(i);
    }
  }
}
vector<int> primeFactors(int x) {
  vector<int> factors;
  long long PF_idx = 0, PF = primes[PF_idx];
  while (PF * PF <= x) {
    if (x % PF == 0) {
      factors.push_back(PF);
      while (x % PF == 0) x /= PF;
    }
    PF = primes[++PF_idx];
  }
  if (x != 1) factors.push_back(x);
  return factors;
}
long long get_multiples(long long lo, long long hi, long long div) {
  return (hi / div - lo / div);
}
int q;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  sieve();
  cin >> q;
  while (q--) {
    int x, p, k;
    cin >> x >> p >> k;
    vector<int> v = primeFactors(p);
    int n = v.size();
    long long lo = x + 1, hi = 1e18, mid, ans = -1;
    vector<pair<int, bool>> tmp;
    for (int i = 1; i < (1 << n); ++i) {
      long long product = 1, mnawar = 0;
      for (int j = 0; j < n; ++j)
        if ((i & (1 << j))) ++mnawar, product *= v[j];
      tmp.emplace_back(product, (mnawar & 1));
    }
    while (lo <= hi) {
      mid = lo + hi >> 1;
      long long sum = 0;
      for (auto &it : tmp)
        sum += (it.second ? 1 : -1) * get_multiples(x, mid, it.first);
      if (mid - sum - x >= k)
        ans = mid, hi = mid - 1;
      else
        lo = mid + 1;
    }
    cout << ans << '\n';
  }
  return 0;
}
