#include <bits/stdc++.h>
using namespace std;
long long x, p, k;
vector<long long> vec;
long long cal(long long n) {
  long long sum = 0;
  int num = vec.size();
  for (int i = 1; i < (1 << num); i++) {
    long long tmp = 1, t = 0;
    for (int j = 0; j < num; j++)
      if ((1 << j) & i) t++, tmp *= vec[j];
    if (t & 1)
      sum += n / tmp;
    else
      sum -= n / tmp;
  }
  return n - sum;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%lld%lld%lld", &x, &p, &k);
    vec.clear();
    for (long long i = 2; i * i <= p; i++) {
      if (p % i == 0) vec.push_back(i);
      while (p % i == 0) p /= i;
    }
    if (p > 1) vec.push_back(p);
    k += cal(x);
    long long l = 1, r = 1e12;
    long long ans = -1;
    while (l <= r) {
      long long m = (l + r) / 2;
      if (cal(m) >= k) {
        ans = m;
        r = m - 1;
      } else
        l = m + 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
