#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > vect, vect2;
vector<int> w[1000005];
bool ciur[1000000 + 5];
int dp[1000000 + 5];
int x, y, tst;
int t;
inline void Prepare() {
  vect.clear();
  int n = (int)w[y].size();
  for (int i = 1; i < (1 << n); i++) {
    int semn = 0;
    long long p = 1LL;
    for (int j = 0; j < n; j++)
      if (i & (1 << j)) {
        semn++;
        p = p * 1LL * w[y][j];
      }
    if (semn % 2)
      vect.push_back({p, 1});
    else
      vect.push_back({p, -1});
  }
  sort(vect.begin(), vect.end());
  vect2.clear();
  for (vector<pair<int, int> >::iterator it = vect.begin(); it != vect.end();
       it++) {
    if (vect2.empty() || vect2.back() != *it) vect2.push_back(*it);
  }
  vect.clear();
  for (auto it : vect2) vect.push_back(it);
}
inline long long f(long long val) {
  long long sol = 0;
  for (vector<pair<int, int> >::iterator it = vect.begin(); it != vect.end();
       it++) {
    sol = sol + (val / (1LL * it->first)) * 1LL * it->second;
  }
  return sol;
}
int k;
int main() {
  for (int i = 4; i <= 1000000; i += 2) {
    ciur[i] = 1;
  }
  for (int i = 3; i <= 1000000; i += 2) {
    if (ciur[i]) continue;
    for (int j = i + i; j <= 1000000; j += i) ciur[j] = 1;
  }
  for (int i = 2; i <= 1000000; i++) {
    if (ciur[i]) continue;
    for (int j = i; j <= 1000000; j += i) {
      {
        int x = j;
        while (x && !(x % i)) {
          x /= i;
        }
        w[j].push_back(i);
      }
    }
  }
  int ts;
  scanf("%d", &ts);
  while (ts--) {
    scanf("%d%d%d", &x, &y, &k);
    vect.clear();
    Prepare();
    long long st, dr, mid, sol = 0LL;
    st = 1LL * x;
    dr = LLONG_MAX;
    long long nr = f(x);
    while (st <= dr) {
      long long mid = st + ((dr - st) >> 1LL);
      if (((mid - x) - (f(mid) - nr)) >= k) {
        sol = mid;
        dr = mid - 1LL;
      } else
        st = mid + 1LL;
    }
    cout << sol << '\n';
  }
  return 0;
}
