#include <bits/stdc++.h>
using namespace std;
constexpr long long size = 1e6 + 10;
vector<long long> A[size];
void prepare(long long);
long long count(long long, long long);
long long upper_bound(long long x, long long p, long long k) {
  long long r = x + 1, q = 1e9;
  int smaller_than_x = count(x, p);
  while (q > r + 1) {
    long long s = (r + q) >> 1;
    long long tmp = count(s, p);
    if (tmp - smaller_than_x < k) {
      r = s;
    } else {
      q = s;
    }
  }
  if (count(r, p) - smaller_than_x == k) return r;
  return q;
}
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
int main() {
  prepare(size);
  long long t, x, p, k;
  cin >> t;
  while (t--) {
    cin >> x >> p >> k;
    int ub = upper_bound(x, p, k);
    cout << ub << endl;
  }
  return 0;
}
void prepare(long long n) {
  for (int i = (int)2; i < (int)n; i++) {
    if (A[i].size() != 0) continue;
    for (int j = (int)i; j < (int)n; j += i) {
      int l = A[j].size();
      for (int k = (int)0; k < (int)l; k++) {
        A[j].push_back(-A[j][k] * i);
      }
      A[j].push_back(i);
    }
  }
}
long long count(long long x, long long p) {
  long long result = 0;
  for (int i = (int)0; i < (int)A[p].size(); i++) {
    result += x / A[p][i];
  }
  return x - result;
}
