#include <bits/stdc++.h>
using namespace std;
int prime[1024], cnt;
bool isprime[1024];
void getprime(int N) {
  for (int i = 2; i <= N; ++i) isprime[i] = 1;
  for (int i = 2; i <= N; ++i) {
    if (isprime[i]) prime[cnt++] = i;
    for (int j = 0, k; k = i * prime[j], j < cnt && k <= N; ++j) {
      isprime[k] = 0;
      if (i % prime[j] == 0) break;
    }
  }
}
int voc[50], num;
int x, p, k;
void solve(int s, int r, int& ans) {
  int mul = 1, tot = 0, i = 0;
  while (i < num && s) {
    if (s & 1) {
      mul *= voc[i];
      if (mul > r) break;
      tot++;
    }
    i++;
    s >>= 1;
  }
  if (tot & 1)
    ans -= r / mul;
  else
    ans += r / mul;
}
int f(int l, int r) {
  int a = l - 1;
  for (int s = 1; s < (1 << num); ++s) solve(s, l - 1, a);
  int b = r;
  for (int s = 1; s < (1 << num); ++s) solve(s, r, b);
  return b - a;
}
int main() {
  getprime(1000);
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &x, &p, &k);
    num = 0;
    int tmpp = p;
    for (int i = 0; i < cnt && prime[i] <= tmpp; ++i) {
      if (tmpp % prime[i] == 0) {
        while (tmpp % prime[i] == 0) tmpp /= prime[i];
        voc[num++] = prime[i];
      }
    }
    if (tmpp != 1) voc[num++] = tmpp;
    int l = x + k, r = 1e8, ans = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (f(x + 1, mid) >= k)
        r = mid - 1, ans = mid;
      else
        l = mid + 1;
    }
    printf("%d\n", ans);
  }
}
