#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
long long cal(long long x) {
  long long ans = 0;
  int num = vec.size();
  int l = 1 << num;
  for (int i = 0; i < (1 << num); i++) {
    long long now = 1, flag = 1;
    for (int j = 0; j < num; j++) {
      if ((i >> j) & 1) {
        now *= vec[j];
        flag *= -1;
      }
    }
    ans += flag * (x / now);
  }
  return ans;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    long long x, p, k;
    scanf("%lld %lld %lld", &x, &p, &k);
    vec.clear();
    for (long long i = 2; i * i <= p; i++) {
      if (p % i == 0) vec.push_back(i);
      while (p % i == 0) p /= i;
    }
    if (p > 1) vec.push_back(p);
    k += cal(x);
    long long l = 1, r = 1e12;
    long long ans = -1;
    while (l <= r) {
      long long m = (r + l) / 2;
      if (cal(m) >= k)
        ans = m, r = m - 1;
      else
        l = m + 1;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
