#include <bits/stdc++.h>
using namespace std;
const long long NR = 15;
long long n;
long long a[NR];
long long siz[1005];
long long solve(long long x, long long p) {
  n = 0;
  for (long long i = 2; i * i <= p; i++) {
    if (p % i) continue;
    a[++n] = i;
    while (!(p % i)) p /= i;
  }
  long long ans = 0;
  if (p != 1) a[++n] = p;
  for (long long i = 1; i < (1 << n); i++) {
    long long t = siz[i] % 2 ? 1 : -1, s = 1;
    for (long long j = 1; j <= n; j++)
      if (i & (1 << j - 1)) s *= a[j];
    ans += (x / s) * t;
  }
  return x - ans;
}
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
signed main() {
  for (long long i = 1; i <= 1000; i++) siz[i] = siz[i / 2] + (i % 2);
  long long T = read();
  while (T--) {
    long long x = read(), p = read(), k = read();
    long long now = solve(x, p);
    k += now;
    long long l = x + 1, r = 1000000000000, ans = -1;
    while (l <= r) {
      long long mid = (l + r >> 1);
      if (solve(mid, p) >= k)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%lld\n", ans % (1000000007));
  }
  return 0;
}
