#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
const int iinf = 1 << 29;
const long long inf = 1ll << 60;
const long long mod = 1e9 + 7;
void GG() {
  cout << "No\n";
  exit(0);
}
long long mpow(long long a, long long n) {
  long long re = 1;
  while (n > 0) {
    if (n & 1) re = re * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return re;
}
long long inv(long long b) {
  if (b == 1) return b;
  return (mod - mod / b) * inv(mod % b) % mod;
}
const int maxn = 1e6 + 5;
vector<int> pfac[maxn];
bool prm[maxn];
void build() {
  fill(prm, prm + maxn, 1);
  for (int i = (2); i < (maxn); i++) {
    if (prm[i]) {
      for (int j = i; j < maxn; j += i) {
        prm[j] = 0;
        pfac[j].push_back(i);
      }
    }
  }
}
long long nles(int x, int p) {
  int m = pfac[p].size();
  long long re = 0;
  for (int i = (1); i < (1 << (m)); i++) {
    long long mul = 1;
    for (int j = 0; j < (m); j++) {
      if (i & (1 << j)) {
        mul *= pfac[p][j];
      }
    }
    mul = x / mul;
    if (__builtin_popcount(i) & 1) {
      re += mul;
    } else {
      re -= mul;
    }
  }
  return x - re;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  build();
  int t;
  cin >> t;
  while (t--) {
    long long x, p, k;
    cin >> x >> p >> k;
    int nx = nles(x, p);
    k += nx;
    long long l = 0, r = 10000000;
    while (l != r) {
      long long mid = (l + r) >> 1;
      if (nles(mid, p) < k) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    cout << r << '\n';
  }
}
