#include <bits/stdc++.h>
using namespace std;
const int maxa = (1 << 8) + 10, maxn = 1000 * 1000 + 100;
long long dp[maxa], ted[maxa], ls[maxn], fir[maxa], p[70];
inline long long get(long long n, long long x) {
  int t, s = 0;
  vector<int> V;
  while (n > 1) {
    if (s == 0 or V.back() != ls[n]) V.push_back(ls[n]), s++;
    n /= ls[n];
  }
  t = 1 << s;
  long long ret = x;
  dp[0] = 1;
  for (int mask = 1; mask < t; mask++) {
    int l = fir[mask];
    dp[mask] = V[l] * dp[mask ^ p[l]];
    if (ted[mask] & 1)
      ret -= x / dp[mask];
    else
      ret += x / dp[mask];
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = (1 << 8) + 10;
  for (int i = 1; i < T; i++) ted[i] = ted[i / 2] + (i & 1);
  for (int i = 1; i < T; i++) fir[i] = i & 1 ? 0 : fir[i / 2] + 1;
  p[0] = 1;
  for (int i = 1; i < 64; i++) p[i] = p[i - 1] * 2;
  for (int i = 2; i < maxn; i++)
    if (ls[i] == 0)
      for (int j = i; j < maxn; j += i) ls[j] = i;
  scanf("%d", &T);
  while (T--) {
    int x, p, k, now;
    scanf("%I64d%I64d%I64d", &x, &p, &k);
    now = get(p, x);
    long long l = 1, r = 2;
    while (get(p, r) < k + now) r = 2 * r, l = 2 * l;
    while (r - l > 1) {
      long long mid = (l + r) / 2;
      if (get(p, mid) >= k + now)
        r = mid;
      else
        l = mid;
    }
    printf("%lld\n", r);
  }
  return 0;
}
