#include <bits/stdc++.h>
using namespace std;
vector<int> p[1000005];
int x, h, k, t, l, r, m, i, j;
pair<int, int> v[128];
int calc(int a) {
  int c = 1, n = 0, z = a;
  for (i = 1; i < 1 << p[h].size(); i++) {
    if (c * 2 == i) c *= 2, n++;
    v[i] = {v[i - c].first * p[h][n], v[i - c].second + 1};
    z += (v[i].second % 2 ? -1 : 1) * a / v[i].first;
  }
  return z;
}
int main() {
  for (i = 2; i < 1000005; i++)
    if (!p[i].size())
      for (j = i; j < 1000005; j += i) p[j].push_back(i);
  v[0] = {1, 0};
  cin >> t;
  while (t--) {
    cin >> x >> h >> k;
    k += calc(x);
    l = 0, r = 7 * 1000005;
    while (l < r) {
      m = (l + r) / 2;
      if (calc(m) >= k)
        r = m;
      else
        l = m + 1;
    }
    cout << l << endl;
  }
}
