#include <bits/stdc++.h>
using namespace std;
const long long int infinito = 10000000000LL;
const int limite = 1000005;
int esprimo[limite];
vector<int> primos[limite];
long long int cuantos(long long int y, long long int p) {
  vector<int> &v = primos[p];
  int n = int(v.size());
  int sol = 0;
  for (int c = 1; c < 1 << n; c++) {
    long long int prod = 1;
    int num1 = 0;
    for (int b = 0; b < n; b++) {
      if (c & (1 << b)) {
        num1++;
        prod *= v[b];
      }
    }
    long long int act = y / prod;
    if (num1 & 1)
      sol += act;
    else
      sol -= act;
  }
  return sol;
}
long long int calcula(long long int x, long long int p, long long int k) {
  long long int menx = cuantos(x, p);
  long long int inf = x;
  long long int sup = infinito;
  while (inf + 1 < sup) {
    long long int med = (inf + sup) / 2;
    long long int c = cuantos(med, p);
    if ((med - x) - (c - menx) >= k)
      sup = med;
    else
      inf = med;
  }
  return sup;
}
int main() {
  for (int i = 2; i < limite; i++) esprimo[i] = 1;
  for (int i = 2; i < limite; i++) {
    if (esprimo[i]) {
      primos[i].push_back(i);
      for (int j = i + i; j < limite; j += i) {
        esprimo[j] = 0;
        primos[j].push_back(i);
      }
    }
  }
  int casos;
  cin >> casos;
  for (int cas = 0; cas < casos; cas++) {
    int x, p, k;
    cin >> x >> p >> k;
    cout << calcula(x, p, k) << endl;
  }
}
