#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 1001005;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
int p[N], prime[N], phi[N], top, T, X, P, K, pp[N];
long long l, r, mid, ans;
void init_prime(int N) {
  top = 0, phi[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!p[i]) prime[++top] = i, phi[i] = i - 1;
    for (int j = 1; j <= top; ++j) {
      if ((long long)i * prime[j] > N) break;
      p[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
      phi[i * prime[j]] = phi[i] * phi[prime[j]];
    }
  }
}
void init(int x) {
  pp[0] = 0;
  for (int i = 1; i <= top && (long long)prime[i] * prime[i] <= x; i++)
    if (x % prime[i] == 0) {
      pp[++pp[0]] = prime[i];
      while (x % prime[i] == 0) x /= prime[i];
      if (x == 1) return;
      if (!p[x]) {
        pp[++pp[0]] = x;
        return;
      }
    }
  if (x > 1) pp[++pp[0]] = x;
}
void dfs(int k, int op, long long s, long long n, long long &ans) {
  if (k > pp[0]) {
    ans += n / s * op;
    return;
  }
  dfs(k + 1, op, s, n, ans);
  if (s * pp[k] <= n) dfs(k + 1, -op, s * pp[k], n, ans);
}
long long Count(long long x) {
  long long ans = 0;
  dfs(1, 1, 1, x % P, ans);
  return x / P * phi[P] + ans;
}
int main() {
  scanf("%d", &T);
  init_prime(N - 5);
  while (T--) {
    scanf("%d%d%d", &X, &P, &K), init(P);
    K += Count(X), l = 1, r = 1e8;
    while (l <= r) {
      mid = (l + r) >> 1;
      if (Count(mid) >= K)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
