#include <bits/stdc++.h>
using namespace std;
void bruteforce() {}
long long power(long long x, long long y) {
  long long res = 1;
  x = x % 1000000007;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y >> 1;
    x = (x * x) % 1000000007;
  }
  return res;
}
long long modInverse(long long n) { return power(n, 1000000007 - 2); }
long long primes[1000100];
int main() {
  ios::sync_with_stdio(0);
  long long tc = 1;
  cin >> tc;
  for (long long i = 2; i < 1000100; i++) {
    if (!primes[i]) {
      for (long long j = i * i; j < 1000100; j += i) primes[j] = i;
    }
  }
  for (int tci = 1; tci < tc + 1; tci++) {
    long long x, p, k;
    cin >> x >> p >> k;
    if (p == 1) {
      cout << x + k << endl;
      continue;
    }
    set<long long> s;
    long long pp = primes[p];
    while (primes[p]) {
      s.insert(pp);
      p /= pp;
      pp = primes[p];
    }
    s.insert(p);
    vector<long long> v;
    for (auto ss : s) v.push_back(ss);
    long long d = v.size();
    long long l = x + 1, r = 1e8;
    long long ans = 0;
    while (l <= r) {
      long long mid = (l + r) / 2;
      long long u = mid - x;
      for (int i = 1; i < (1ll << d); i++) {
        long long num = 1;
        for (int j = 0; j < d; j++) {
          if (i & (1ll << j)) {
            num *= v[j];
          }
        }
        long long o = __builtin_popcount(i);
        if (o % 2 == 0)
          u += (mid / num) - (x / num);
        else
          u -= (mid / num) - (x / num);
      }
      if (u >= k)
        r = mid - 1;
      else if (u < k)
        l = mid + 1;
      if (u == k) ans = mid;
    }
    if (ans == 0) cout << x << "00" << p << "00" << k << endl;
    cout << ans << endl;
  }
  return 0;
}
