#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f ? -x : x;
}
const int N = 1e6 + 100;
int P[60];
int Solve(int x, int a, int type) {
  if (a == P[0] + 1) {
    return x * type;
  } else {
    return Solve(x, a + 1, type) + Solve(x / P[a], a + 1, type * -1);
  }
}
int solve(int x) { return Solve(x, 1, 1); }
int main() {
  int T = read();
  while (T--) {
    int limit = read(), p = read(), k = read();
    P[0] = 0;
    int x = p;
    for (int i = 2; i * i <= x; i++) {
      if (x % i) continue;
      P[++P[0]] = i;
      while (!(x % i)) x = x / i;
    }
    if (x > 1) P[++P[0]] = x;
    k += solve(limit);
    int l = limit + 1, r = 1e9, ans = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      x = solve(mid);
      if (x >= k)
        r = mid - 1, ans = mid;
      else
        l = mid + 1;
    }
    cout << ans << endl;
  }
}
