#include <bits/stdc++.h>
using namespace std;
const int LOGX = 10;
const int MULT_SIZE = 150;
int p[LOGX], multp[MULT_SIZE], multn[MULT_SIZE];
int size_p, size_multp, size_multn;
void fact(int x) {
  int t = sqrt(x);
  size_p = 0;
  for (int i = 2; i <= t && x > 1; i++) {
    if (x % i != 0) continue;
    while (x % i == 0) x /= i;
    p[size_p++] = i;
  }
  if (x > 1) p[size_p++] = x;
}
void init_mult() {
  size_multn = size_multp = 0;
  for (int j = 0; j < (1 << size_p); j++) {
    int mask = j, k = 0, mult = 1;
    for (int i = 0; i < size_p; i++) {
      if (mask % 2 == 1) {
        mult *= p[i];
        k++;
      }
      mask >>= 1;
    }
    if (k % 2 == 0)
      multp[size_multp++] = mult;
    else
      multn[size_multn++] = mult;
  }
}
int f(int n) {
  int ans = 0;
  for (int i = 0; i < size_multp; i++) ans += n / multp[i];
  for (int i = 0; i < size_multn; i++) ans -= n / multn[i];
  return ans;
}
int bin_s(int l, int r, int x) {
  while (l < r) {
    int m = (l + r) / 2;
    if (f(m) >= x)
      r = m;
    else
      l = m + 1;
  }
  return l;
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int x, p, k;
    cin >> x >> p >> k;
    fact(p);
    init_mult();
    k += f(x);
    cout << bin_s(1, 1e9, k) << "\n";
  }
  return 0;
}
