#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
int q, lp[N];
vector<int> v;
int get(int x) {
  int ret = 0;
  int sz = v.size();
  for (int mask = 1; mask < (1 << sz); mask++) {
    int bit = __builtin_popcount(mask), b = 1;
    for (int i = 0; i < sz; i++) {
      if ((mask >> i) & 1) b *= v[i];
    }
    if (bit & 1)
      ret += x / b;
    else
      ret -= x / b;
  }
  return x - ret;
}
bool cnt(int a, int x, int k) { return get(a) - get(x) >= k; }
int main() {
  for (int i = 2; i < N; i++) {
    if (!lp[i]) {
      for (int j = i; j < N; j += i) lp[j] = i;
    }
  }
  scanf("%d", &q);
  while (q--) {
    int x, p, k;
    scanf("%d %d %d", &x, &p, &k);
    v.clear();
    while (p > 1) {
      if (v.empty() || v.back() != lp[p]) v.push_back(lp[p]);
      p /= lp[p];
    }
    int lo = 1, hi = 1e8;
    while (hi - lo > 1) {
      int md = (lo + hi) >> 1;
      if (cnt(md, x, k))
        hi = md;
      else
        lo = md;
    }
    if (cnt(lo, x, k)) hi = lo;
    printf("%d\n", hi);
  }
}
