#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:536870912")
#pragma warning(disable : 4996)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int N = 1e6 + 100;
vector<int> d[N];
int c[N];
long long int f(long long int n, long long int p) {
  long long int ans = n;
  for (int i : d[p]) {
    ans = ans + (n / i) * (c[i] ? -1 : 1);
  }
  return ans;
}
int main() {
  for (int i = 2; i < N; i++) {
    for (int j = 2; j * j <= i; j++) {
      if (i % j == 0) {
        int q = i / j;
        c[i] = c[q];
        d[i] = d[q];
        if (q % j) {
          for (int k = (int)d[i].size() - 1; k >= 0; k--)
            d[i].push_back(d[i][k] * j);
          d[i].push_back(j);
          c[i] ^= 1;
        }
        break;
      }
    }
    if (d[i].empty()) {
      d[i].push_back(i);
      c[i] = 1;
    }
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int x, p, k;
    scanf("%d%d%d", &x, &p, &k);
    long long int l = 0, r = 1e17, b = f(x, p);
    while (r - l > 1) {
      long long int m = (r + l) >> 1;
      if (f(m, p) - b >= k)
        r = m;
      else
        l = m;
    }
    printf("%lld\n", r);
  }
  return 0;
}
