#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
bool isp[N];
int P[N / 10], f[N], cnt;
void init() {
  memset(isp, 1, sizeof(isp));
  isp[0] = isp[1] = 0;
  f[1] = 1;
  for (int i = 2; i <= 1000000; ++i) {
    if (isp[i]) {
      P[++cnt] = i;
      f[i] = i;
    }
    for (int t, j = 1; j <= cnt; ++j) {
      if ((t = P[j] * i) > 1000000) break;
      isp[t] = 0;
      f[t] = P[j];
      if (!(i % P[j])) break;
    }
  }
}
int T, x, p, k;
int cc, tmp[30];
int calc(int x) {
  int ans = 0;
  for (int i = 0; i < (1 << cc); ++i) {
    int mul = 1;
    int cnt = 0;
    for (int j = 0; j < cc; ++j)
      if ((i >> j) & 1) ++cnt, mul *= tmp[j];
    if (cnt & 1)
      ans -= x / mul;
    else
      ans += x / mul;
  }
  return ans;
}
int solve() {
  cc = 0;
  for (int tt = p; tt > 1; tt = tt / f[tt]) tmp[cc++] = f[tt];
  cc = unique(tmp, tmp + cc) - tmp;
  k += calc(x);
  int l = x + 1, r = 1e9, mid;
  while (l <= r) {
    mid = l + r >> 1;
    if (calc(mid) >= k)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  init();
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &x, &p, &k);
    printf("%d\n", solve());
  }
  return 0;
}
