#include <bits/stdc++.h>
using namespace std;
char buf[1 << 20], *_ = buf, *__ = buf;
template <class T>
inline bool read(T &x) {
  x = 0;
  char c = (_ == __ && (__ = (_ = buf) + fread(buf, 1, 1 << 20, stdin), _ == __)
                ? EOF
                : *_++);
  bool f = 0;
  while (c < 48 || c > 57) {
    if (c == EOF) return 0;
    f ^= (c == '-'),
        c = (_ == __ &&
                     (__ = (_ = buf) + fread(buf, 1, 1 << 20, stdin), _ == __)
                 ? EOF
                 : *_++);
  }
  while (47 < c && c < 58)
    x = (x << 3) + (x << 1) + (c ^ 48),
    c = (_ == __ && (__ = (_ = buf) + fread(buf, 1, 1 << 20, stdin), _ == __)
             ? EOF
             : *_++);
  if (f) x = -x;
  return 1;
}
template <class T>
inline bool read(T &a, T &b) {
  return read(a) && read(b);
}
template <class T>
inline bool read(T &a, T &b, T &c) {
  return read(a) && read(b) && read(c);
}
int voc[50];
int x, p, k;
int dfs(int i, int tot, int mul, int n) {
  if (i > *voc || mul > n) return (tot & 1) ? -n / mul : n / mul;
  return dfs(i + 1, tot, mul, n) + dfs(i + 1, tot + 1, mul * voc[i], n);
}
int getans(int l, int r) { return dfs(1, 0, 1, r) - dfs(1, 0, 1, l - 1); }
int main() {
  int t;
  read(t);
  while (t--) {
    read(x, p, k);
    *voc = 0;
    int tmpp = p;
    for (int i = 2; i * i <= tmpp; ++i) {
      if (tmpp % i == 0) {
        while (tmpp % i == 0) tmpp /= i;
        voc[++*voc] = i;
      }
    }
    if (tmpp != 1) voc[++*voc] = tmpp;
    int l = x + k, r = x + 10 * k, ans = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (getans(x + 1, mid) >= k)
        r = mid - 1, ans = mid;
      else
        l = mid + 1;
    }
    printf("%d\n", ans);
  }
}
