func_code_string: #include <bits/stdc++.h>   using namespace std;   const int oo = 0x3f3f3f3f;   const long long ooo = 9223372036854775807ll;   const int _cnt = 1000 * 1000 + 7;   const int _p = 1000 * 1000 * 1000 + 7;   const int N = 1001005;   const double PI = acos(-1.0);   const double eps = 1e-9;   int o(int x) { return x % _p; }   int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }   int lcm(int a, int b) { return a / gcd(a, b) * b; }   void file_put() {     freopen( filename.in ,  r , stdin);     freopen( filename.out ,  w , stdout);   }   int p[N], prime[N], phi[N], top, T, X, P, K, pp[N];   long long l, r, mid, ans;   void init_prime(int N) {     top = 0, phi[1] = 1;     for (int i = 2; i <= N; ++i) {       if (!p[i]) prime[++top] = i, phi[i] = i - 1;       for (int j = 1; j <= top; ++j) {         if ((long long)i * prime[j] > N) break;         p[i * prime[j]] = 1;         if (i % prime[j] == 0) {           phi[i * prime[j]] = phi[i] * prime[j];           break;         }         phi[i * prime[j]] = phi[i] * phi[prime[j]];       }     }   }   void init(int x) {     pp[0] = 0;     for (int i = 1; i <= top && (long long)prime[i] * prime[i] <= x; i++)       if (x % prime[i] == 0) {         pp[++pp[0]] = prime[i];         while (x % prime[i] == 0) x /= prime[i];         if (x == 1) return;         if (!p[x]) {           pp[++pp[0]] = x;           return;         }       }     if (x > 1) pp[++pp[0]] = x;   }   void dfs(int k, int op, long long s, long long n, long long &ans) {     if (k > pp[0]) {       ans += n / s * op;       return;     }     dfs(k + 1, op, s, n, ans);     if (s * pp[k] <= n) dfs(k + 1, -op, s * pp[k], n, ans);   }   long long Count(long long x) {     long long ans = 0;     dfs(1, 1, 1, x % P, ans);     return x / P * phi[P] + ans;   }   int main() {     scanf( %d , &T);     init_prime(N - 5);     while (T--) {       scanf( %d%d%d , &X, &P, &K), init(P);       K += Count(X), l = 1, r = 1e8;       while (l <= r) {         mid = (l + r) >> 1;         if (Count(mid) >= K)           ans = mid, r = mid - 1;         else           l = mid + 1;       }       printf( %I64d n , ans);     }     return 0;   }   