#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, inf = 1e9 + 7;
int n, k, i, j;
bool p[N], u[N];
vector<int> v[N], fac[N];
int util(int p, int first) {
  int num = first;
  for (auto i : fac[p]) {
    if (u[i])
      num -= first / i;
    else
      num += first / i;
  }
  return num;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int i, j, a, b, ans = 0, t, first, k;
  for (i = 2; i < N; i++)
    if (!p[i])
      for (int j = i; j < N; j += i) p[j] = 1, v[j].emplace_back(i);
  for (i = 2; i < N; i++) {
    for (auto k : v[i]) {
      a = (int)fac[i].size();
      fac[i].emplace_back(k);
      u[k] = 1;
      for (j = 0; j < a; j++)
        fac[i].emplace_back(k * fac[i][j]), u[k * fac[i][j]] = u[fac[i][j]] ^ 1;
    }
  }
  cin >> t;
  while (t--) {
    int p;
    cin >> first >> p >> k;
    k += util(p, first);
    int l = first, h = inf, m;
    ans = l;
    while (l <= h) {
      m = l + h >> 1;
      if (util(p, m) >= k)
        ans = m, h = m - 1;
      else
        l = m + 1;
    }
    cout << ans << "\n";
  }
}
