#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
const int N = 1e8;
const int mod = 1e9 + 7;
using pii = pair<int, int>;
int powm(int a, int b) {
  a = a % mod;
  int res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
std::vector<int> a;
int f(int x, int p) {
  int k = a.size();
  int ans = 0;
  for (int i = 1; i < (1 << k); i++) {
    int k = i;
    int pr = 1;
    int ct = 0;
    int n = 0;
    while (k) {
      if (k % 2) {
        pr *= a[ct];
        n++;
      }
      k /= 2;
      ct++;
    }
    int te = x / pr;
    if (n % 2) {
      ans += te;
    } else {
      ans -= te;
    }
  }
  return x - ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int x, p, k;
      cin >> x >> p >> k;
      int l = 0, r = 10000000;
      for (int i = 2; i < p; i++) {
        if (p % i == 0) {
          while (p % i == 0) {
            p /= i;
          }
          a.push_back(i);
        }
      }
      if (p != 1) {
        a.push_back(p);
        p /= p;
      }
      int base = f(x, p);
      while (l < r) {
        int mid = l + (r - l) / 2;
        if (f(mid, p) - base < k) {
          l = mid + 1;
        } else {
          r = mid;
        }
      }
      cout << l << '\n';
      a.clear();
    }
  }
}
