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