#include <bits/stdc++.h>
using namespace std;
int x, p, k;
vector<int> primoszto(1000001, -1), primek;
void primoszto_szamolas() {
  primoszto[0] = 1;
  primoszto[1] = 1;
  for (int i = 2; i <= 1000000; i++) {
    if (primoszto[i] == -1) {
      primek.push_back(i);
      primoszto[i] = i;
    }
    for (int x : primek) {
      if (i * x > 1000000 || x > primoszto[i]) break;
      primoszto[i * x] = x;
    }
  }
}
int ell(int hely, vector<int> osztok) {
  int vissza = 0;
  for (int mask = 0; mask < (1 << osztok.size()); mask++) {
    int szam = 1, db = 0, index = 0;
    for (int i = 1; i < (1 << osztok.size()); i *= 2) {
      if ((i & mask) != 0) szam *= osztok[index], db++;
      index++;
    }
    if (db % 2 == 0)
      vissza += hely / szam;
    else
      vissza -= hely / szam;
  }
  return vissza;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  primoszto_szamolas();
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> x >> p >> k;
    vector<int> osztok;
    int hely = p;
    while (primoszto[hely] != hely) {
      if (osztok.size() == 0 || osztok.back() != primoszto[hely])
        osztok.push_back(primoszto[hely]);
      hely /= primoszto[hely];
    }
    if (hely > 1 && (osztok.size() == 0 || osztok.back() != hely))
      osztok.push_back(primoszto[hely]);
    int l = 0, r = 1000000000;
    while (l + 1 != r) {
      int koztes = (l + r) / 2;
      if (ell(koztes, osztok) - ell(x, osztok) < k)
        l = koztes;
      else
        r = koztes;
    }
    cout << l + 1 << endl;
  }
  return 0;
}
