#include <bits/stdc++.h>
using namespace std;
const int A = 1000001;
int x, p, k;
bool b[A];
vector<int> v[A];
int calc(int x) {
  int ret = 0;
  int n = v[p].size();
  for (int i = 1; i < (1 << n); i++) {
    int pro = 1;
    for (int j = 0; j < n; j++) {
      if ((1 << j) & i) pro *= v[p][j];
    }
    ret += x / pro * (__builtin_popcount(i) % 2 ? 1 : -1);
  }
  return x - ret;
}
int main() {
  for (int i = 2; i < A; i++) b[i] = 1;
  for (int i = 2; i < A; i++) {
    if (b[i] == 0) continue;
    v[i].push_back(i);
    for (int j = i + i; j < A; j += i) {
      v[j].push_back(i);
      b[j] = 0;
    }
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d", &x, &p, &k);
    int c = calc(x);
    int l = 1, r = 1e9;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (calc(mid) - c >= k)
        r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%d\n", r + 1);
  }
}
