#include <bits/stdc++.h>
using namespace std;
using INT = long long;
const int NN = 1000100;
vector<int> dv[NN];
int w[NN], prime[NN];
int s[NN];
INT calc(INT mx, int p) {
  INT ans = 0;
  for (int u : dv[s[p]]) {
    ans += (INT)w[u] * (mx / u);
  }
  return ans;
}
int main() {
  w[1] = 1;
  for (int i = 2; i < NN; i++)
    if (prime[i] == 0) {
      for (int j = i; j < NN; j += i) prime[j] = i;
    }
  s[1] = 1;
  for (int i = 2; i < NN; i++) {
    if (i / prime[i] % prime[i] == 0)
      w[i] = 0, s[i] = s[i / prime[i]];
    else
      w[i] = -w[i / prime[i]], s[i] = s[i / prime[i]] * prime[i];
  }
  for (int i = 1; i < NN; i++) {
    if (w[i]) {
      for (int j = i; j < NN; j += i)
        if (w[j]) dv[j].push_back(i);
    }
  }
  int T;
  cin >> T;
  while (T--) {
    int x, p, k;
    scanf("%d %d %d", &x, &p, &k);
    int num = calc(x, p);
    INT st = x, ed = 1e7;
    while (st + 1 < ed) {
      INT md = (st + ed) / 2;
      if (calc(md, p) - num < k)
        st = md;
      else
        ed = md;
    }
    printf("%I64d\n", ed);
  }
}
