#include <bits/stdc++.h>
using namespace std;
const int MX = 1000 * 1000 + 7;
const int MP = 15;
bool p[MX];
int lp[MX];
int mmul[1 << MP];
int ml[1 << MP];
int calc(int l, int r, int x) { return r / x - (l - 1) / x; }
void solve(int x, int p, int k) {
  vector<int> pr;
  while (p > 1) {
    pr.push_back(lp[p]);
    p /= lp[p];
  }
  sort(pr.begin(), pr.end());
  pr.resize(unique(pr.begin(), pr.end()) - pr.begin());
  int lg = x, rg = 1e9 + 7;
  mmul[0] = 1;
  ml[0] = 1;
  int sz = pr.size();
  for (int mask = 1; mask < (1 << sz); mask++) {
    for (int i = 0; i < pr.size(); i++) {
      if (mask & (1 << i)) {
        mmul[mask] = mmul[mask ^ (1 << i)] * pr[i];
        ml[mask] = ml[mask ^ (1 << i)] * -1;
      }
    }
  }
  while (rg - lg > 1) {
    int mg = (lg + rg) >> 1;
    int cnt = 0;
    for (int i = 0; i < (1 << sz); i++) {
      cnt += calc(x + 1, mg, mmul[i]) * ml[i];
    }
    if (cnt < k) {
      lg = mg;
    } else {
      rg = mg;
    }
  }
  cout << rg << endl;
}
int main() {
  for (int i = 2; i < MX; i++) {
    p[i] = true;
  }
  for (int i = 2; i < MX; i++) {
    if (p[i]) {
      for (int j = i; j < MX; j += i) {
        p[j] = false;
        lp[j] = i;
      }
    }
  }
  int t;
  cin >> t;
  for (int tt = 1; tt <= t; tt++) {
    int x, p, k;
    cin >> x >> p >> k;
    solve(x, p, k);
  }
}
