#include <bits/stdc++.h>
using namespace std;
int p[7100000];
int t, x, pp, k;
int main() {
  for (int i = 2; i <= 7000000; i++) {
    if (!p[i]) {
      for (int j = i; j <= 7000000; j += i) {
        if (!p[j]) p[j] = i;
      }
    }
  }
  cin >> t;
  while (t--) {
    int fak[10], cnt = 0;
    cin >> x >> pp >> k;
    int now = pp;
    while (now > 1) {
      fak[cnt++] = p[now];
      int sem = p[now];
      while (now > 1 && now % sem == 0) now /= sem;
    }
    int seb = 0;
    for (int i = 1; i <= (1 << cnt) - 1; i++) {
      int kali = -1;
      if (__builtin_popcount(i) % 2) {
        kali = 1;
      }
      int bil = 1;
      for (int j = 0; j < cnt; j++) {
        if (i & (1 << j)) {
          bil *= fak[j];
        }
      }
      seb += (x / bil) * kali;
    }
    seb = x - seb;
    int lo = x + 1, hi = 7000000, jaw = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      int tot = 0;
      for (int i = 1; i <= (1 << cnt) - 1; i++) {
        int kali = -1;
        if (__builtin_popcount(i) % 2) kali = 1;
        int bil = 1;
        for (int j = 0; j < cnt; j++) {
          if (i & (1 << j)) bil *= fak[j];
        }
        tot += (mid / bil) * kali;
      }
      tot = mid - tot;
      if (tot - seb >= k) {
        hi = mid - 1;
        jaw = mid;
      } else
        lo = mid + 1;
    }
    cout << jaw << endl;
  }
}
