#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int arr[111];
int fir[1000011];
int vst[1000011];
int val[1000011];
void pre() {
  for (int i = 2; i < 1000011; i++)
    if (!vst[i]) {
      fir[i] = i;
      if ((long long)i * i >= 1000011) continue;
      if ((long long)i * i >= 1000011) continue;
      fir[i] = i;
      for (int j = i * i; j < 1000011; j += i) {
        vst[j] = 1;
        if (fir[j] == 0) fir[j] = i;
      }
    }
}
int nn = 0;
int calc(int ed) {
  int ans = 0;
  val[0] = 1;
  for (int i = 0; i < 1 << nn; i++) {
    if (i and i == (i & -i)) {
      for (int j = 0; j < nn; j++) {
        if ((((i) >> (j)) & 1)) {
          val[i] = arr[j];
          break;
        }
      }
    } else if (i)
      val[i] = val[i ^ (i & -i)] * val[i & -i];
    if ((__builtin_popcount(i)) & 1)
      ans -= ed / val[i];
    else
      ans += ed / val[i];
  }
  return ans;
}
int main() {
  int t;
  cin >> t;
  pre();
  while (t--) {
    int first, p, k;
    gn(first);
    gn(p);
    gn(k);
    nn = 0;
    while (p != 1) {
      arr[nn++] = fir[p];
      int v = fir[p];
      while (p % v == 0) p /= v;
    }
    int st = first, mid, ed = 0x3f3f3f3f;
    while (ed > st + 1) {
      mid = st + ed >> 1;
      if (calc(mid) - calc(first) >= k)
        ed = mid;
      else
        st = mid;
    }
    print(ed);
    puts("");
  }
  return 0;
}
