#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
vector<int> cnt[maxn];
bool isPrime[maxn];
long long int gcd(long long int a, long long int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
void init() {
  memset(isPrime, 1, sizeof(isPrime));
  for (int i = 2; i <= maxn - 1; i++) {
    if (!isPrime[i]) continue;
    cnt[i].push_back(i);
    for (int j = 2 * i; j < maxn; j += i) {
      cnt[j].push_back(i);
      isPrime[j] = 0;
    }
  }
}
long long int check(long long int x, int sub, int p) {
  int z = cnt[p].size();
  long long int ans = x;
  z = 1 << z;
  for (int i = 1; i <= z - 1; i++) {
    int num = 1, cnt1 = 0;
    for (int j = 0; j <= (int)cnt[p].size() - 1; j++) {
      if ((1 << j) & i) {
        num *= cnt[p][j];
        cnt1++;
      }
    }
    if (cnt1 % 2) {
      ans -= (x / num);
    } else {
      ans += (x / num);
    }
  }
  return (ans - sub);
}
long long int srch(long long int s, long long int e, int lessThan, int k,
                   int p) {
  if (e >= s) {
    long long int m = (e + s) >> 1;
    if (check(m, lessThan, p) == k and gcd(m, p) == 1) return m;
    if (check(m, lessThan, p) >= k) return srch(s, m - 1, lessThan, k, p);
    return srch(m + 1, e, lessThan, k, p);
  }
}
void solve() {
  init();
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int x, p, k;
    scanf("%d", &x);
    scanf("%d", &p);
    scanf("%d", &k);
    int z = cnt[p].size();
    int ans = x;
    z = 1 << z;
    for (int i = 1; i <= z - 1; i++) {
      int num = 1, cnt1 = 0;
      for (int j = 0; j <= (int)cnt[p].size() - 1; j++) {
        if ((1 << j) & i) {
          num *= cnt[p][j];
          cnt1++;
        }
      }
      if (cnt1 % 2) {
        ans -= (x / num);
      } else {
        ans += (x / num);
      }
    }
    printf("%lld\n", srch(x + 1, 1e9, ans, k, p));
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
