func_code_string: #include <bits/stdc++.h>   using namespace std;   void bruteforce() {}   long long power(long long x, long long y) {     long long res = 1;     x = x % 1000000007;     if (x == 0) return 0;     while (y > 0) {       if (y & 1) res = (res * x) % 1000000007;       y = y >> 1;       x = (x * x) % 1000000007;     }     return res;   }   long long modInverse(long long n) { return power(n, 1000000007 - 2); }   long long primes[1000100];   int main() {     ios::sync_with_stdio(0);     long long tc = 1;     cin >> tc;     for (long long i = 2; i < 1000100; i++) {       if (!primes[i]) {         for (long long j = i * i; j < 1000100; j += i) primes[j] = i;       }     }     for (int tci = 1; tci < tc + 1; tci++) {       long long x, p, k;       cin >> x >> p >> k;       if (p == 1) {         cout << x + k << endl;         continue;       }       set<long long> s;       long long pp = primes[p];       while (primes[p]) {         s.insert(pp);         p /= pp;         pp = primes[p];       }       s.insert(p);       vector<long long> v;       for (auto ss : s) v.push_back(ss);       long long d = v.size();       long long l = x + 1, r = 1e8;       long long ans = 0;       while (l <= r) {         long long mid = (l + r) / 2;         long long u = mid - x;         for (int i = 1; i < (1ll << d); i++) {           long long num = 1;           for (int j = 0; j < d; j++) {             if (i & (1ll << j)) {               num *= v[j];             }           }           long long o = __builtin_popcount(i);           if (o % 2 == 0)             u += (mid / num) - (x / num);           else             u -= (mid / num) - (x / num);         }         if (u >= k)           r = mid - 1;         else if (u < k)           l = mid + 1;         if (u == k) ans = mid;       }       if (ans == 0) cout << x <<  00  << p <<  00  << k << endl;       cout << ans << endl;     }     return 0;   }   