func_code_string: #include <bits/stdc++.h>   using namespace std;   long long calc_gcd(long long a, long long b) {     while (true)       if (a)         b %= a, swap(a, b);       else         return b;   }   void foo() {     long long A, M;     cin >> A >> M;     long long gcd = calc_gcd(A, M);     A /= gcd;     M /= gcd;     set<long long> yakusuu;     long long tmp = M;     while (tmp % 2 == 0) {       yakusuu.insert(2);       tmp /= 2;     }     for (long long i = 3; i * i <= M; i += 2) {       while (tmp % i == 0) {         yakusuu.insert(i);         tmp /= i;       }     }     if (tmp > 1) {       yakusuu.insert(tmp);       tmp = 1;     }     vector<long long> yakusuu_vec;     for (auto it : yakusuu) yakusuu_vec.push_back(it);     long long limit = 1;     limit <<= yakusuu_vec.size();     long long foo = 0;     long long bar = 0;     for (long long i = 0; i < limit; i++) {       long long tmp = 1;       long long count = 0;       for (long long k = 0; k < (yakusuu_vec.size()); k++) {         if (((i >> k) & 1) == 1) {           tmp *= yakusuu_vec[k];           count++;         }       }       if (count % 2) {         foo -= (A + M - 1) / tmp;         bar -= (A - 1) / tmp;       } else {         foo += (A + M - 1) / tmp;         bar += (A - 1) / tmp;       }     }     cout << (foo - bar) << endl;   }   void solve() {     long long T;     cin >> T;     for (long long t = 0; t < (T); t++) foo();   }   int main(void) {     cin.tie(0);     ios::sync_with_stdio(false);     cout.precision(12);     cout << fixed;     solve();     return 0;   }   