#include <bits/stdc++.h>
using namespace std;
vector<int> pr[1000005];
int ok[1000005];
int x, p, k;
long long solve(long long mid) {
  int cnt = pr[p].size();
  long long res = mid;
  long long res2 = x;
  for (int i = 1; i < (1 << cnt); i++) {
    int ok = 0;
    long long num = 1;
    for (int j = 0; j < cnt; j++) {
      if (i & (1 << j)) {
        ok = !ok;
        num = num * pr[p][j];
      }
    }
    if (ok) {
      res -= mid / num;
      res2 -= x / num;
    } else {
      res += mid / num;
      res2 += x / num;
    }
  }
  res -= res2;
  return res >= k;
}
int main() {
  for (int i = 2; i <= 1000000; i++) {
    if (!ok[i]) {
      for (int j = i; j <= 1000000; j += i) {
        pr[j].push_back(i);
        ok[j] = 1;
      }
    }
  }
  int t;
  cin >> t;
  while (t--) {
    scanf("%d%d%d", &x, &p, &k);
    if (p == 1) {
      cout << x + k << endl;
      continue;
    }
    long long st = 1, En = 1e7;
    long long ans = 1e7;
    while (st <= En) {
      long long mid = (st + En) / 2;
      if (solve(mid)) {
        ans = mid;
        En = mid - 1;
      } else {
        st = mid + 1;
      }
    }
    printf("%I64d\n", ans);
  }
}
