#include <bits/stdc++.h>
using namespace std;
vector<long long> factors;
vector<pair<int, long long> > prod;
const long long infy = 1e18;
void genProd(int pos = 0, long long val = 1, int count = 0) {
  if (pos == factors.size()) {
    if (val != 1) prod.push_back({count, val});
    return;
  }
  genProd(pos + 1, val, count);
  genProd(pos + 1, val * factors[pos], count + 1);
}
long long func(long long lim) {
  long long val = 0;
  for (auto u : prod) {
    long long temp = lim / u.second;
    if (u.first & 1)
      val += temp;
    else
      val -= temp;
  }
  val = lim - val;
  return val;
}
long long first, p, k;
long long base;
const int maxprime = 1e6 + 10, up = sqrt(maxprime);
int prime[maxprime];
inline void sieve() {
  for (int i = 0; i < maxprime; i++) prime[i] = i;
  for (int i = 2; i < maxprime; i += 2) prime[i] = 2;
  for (int i = 3; i <= up; i += 2) {
    if (prime[i] != i) continue;
    int lim = i * i;
    int add = 2 * i;
    for (int j = lim; j < maxprime; j += add) {
      if (prime[j] == j) prime[j] = i;
    }
  }
}
void prep() {
  factors.clear();
  prod.clear();
  long long temp = p;
  long long fact;
  while (temp > 1) {
    fact = prime[temp];
    while (temp % fact == 0) temp /= fact;
    factors.push_back(fact);
  }
  genProd();
}
long long bsrch(long long l, long long r) {
  if (l == r) return l;
  long long mid = (l + r) / 2;
  if ((func(mid) - base) >= k)
    return bsrch(l, mid);
  else
    return bsrch(mid + 1, r);
}
void solve() {
  cin >> first >> p >> k;
  if (p == 1) {
    cout << first + k;
    return;
  }
  prep();
  base = func(first);
  cout << bsrch(first + 1, infy);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  sieve();
  int t;
  cin >> t;
  while (t--) {
    solve();
    cout << '\n';
  }
  return 0;
}
