#include <bits/stdc++.h>
using namespace std;
int k, x;
vector<int> primefactors;
vector<int> plusfactors;
vector<int> minusfactors;
void calc(int i, int cnt, int pro) {
  if (i == primefactors.size()) {
    if (pro != 1) {
      if (cnt % 2)
        plusfactors.push_back(pro);
      else
        minusfactors.push_back(pro);
    }
    return;
  }
  calc(i + 1, cnt, pro);
  calc(i + 1, cnt + 1, pro * primefactors[i]);
}
long long get(long long r) {
  int i;
  long long cnt = 0;
  for (i = 0; i < plusfactors.size(); ++i)
    cnt += ((r / plusfactors[i]) - (x / plusfactors[i]));
  for (i = 0; i < minusfactors.size(); ++i)
    cnt -= ((r / minusfactors[i]) - (x / minusfactors[i]));
  return (r - cnt - x);
}
int main() {
  int t, i, p;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d %d", &x, &p, &k);
    int s = sqrt(p);
    for (i = 2; i <= s; ++i) {
      if (!(p % i)) primefactors.push_back(i);
      while (!(p % i)) p /= i;
    }
    if (p > 1) primefactors.push_back(p);
    calc(0, 0, 1);
    long long cnt, low = x + 1, up = 1e7, mid;
    while (low <= up) {
      mid = (up + low) / 2;
      cnt = get(mid);
      if (cnt >= k)
        up = mid - 1;
      else
        low = mid + 1;
    }
    printf("%lld\n", low);
    primefactors.clear();
    plusfactors.clear();
    minusfactors.clear();
  }
  return 0;
}
