#include <bits/stdc++.h>
using namespace std;
vector<int> v;
vector<pair<long long, long long> > lst;
long long f(long long x, int p) {
  long long ans = 0;
  for (int i = 0; i < lst.size(); ++i) {
    ans += lst[i].second * x / lst[i].first;
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int x, p, k;
    cin >> x >> p >> k;
    v.clear();
    for (int i = 2; i * i <= p; ++i) {
      if (p % i > 0) continue;
      v.push_back(i);
      while (p % i == 0) p /= i;
    }
    if (p > 1) v.push_back(p);
    lst.clear();
    for (int i = 0; i < (1 << v.size()); ++i) {
      int res = 1, cnt = 0;
      for (int j = 0; j < v.size(); ++j) {
        if (i & (1 << j)) {
          res *= v[j];
          ++cnt;
        }
      }
      if (cnt % 2 == 0)
        lst.push_back(make_pair(res, 1));
      else
        lst.push_back(make_pair(res, -1));
    }
    int base = f(x, p);
    long long l = 1, r = 1e18;
    while (l < r) {
      long long m = (l + r) / 2;
      long long res = f(m, p);
      if (res - base >= k) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    cout << l << endl;
  }
  return 0;
}
