#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int M = 1e6 + 10;
vector<int> prim[M + 6];
void init() {
  for (int i = 2; i <= M; i++) {
    if (prim[i].size() == 0) {
      for (int j = i; j <= M; j += i) prim[j].push_back(i);
    }
  }
}
int solve(int x, int p) {
  int n = prim[p].size();
  int res = 0;
  for (int i = 1; i < (1 << n); i++) {
    int sum = 1, num = 0;
    for (int j = 0; j < n; j++)
      if ((i >> j) & 1) sum *= prim[p][j], num++;
    int tmp = x / sum;
    if (num & 1)
      res += tmp;
    else
      res -= tmp;
  }
  return x - res;
}
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    int x, p, k;
    scanf("%d%d%d", &x, &p, &k);
    int fir = solve(x, p);
    int l = x, r = inf, ans;
    while (l <= r) {
      int midd = (l + r) >> 1;
      if (solve(midd, p) - fir >= k) {
        ans = midd;
        r = midd - 1;
      } else
        l = midd + 1;
    }
    printf("%d\n", ans);
  }
  return 0;
}
