Problem Definition

Given two positive integers base and modulus where base < modulus, determine the count of non-negative integers x such that 0 ≤ x < modulus and gcd(base, modulus) == gcd(base + x, modulus).

Input Constraints

• Number of test cases: 1 ≤ T ≤ 50
• Value range: 1 ≤ base < modulus ≤ 10^{10}

Mathematical Reduction

Let d = gcd(base, modulus). The condition gcd(base + x, modulus) = d implies that d must divide base + x. Since d inherently divides base, it follows that d must also divide x.

By normalizing all terms with respect to d, we define: base' = base / d, modulus' = modulus / d, and x' = x / d.

The original requirement simplifies to finding x' where gcd(base' + x', modulus') = 1. As x iterates through [0, modulus - 1], the transformed variable x' covers [0, modulus' - 1]. Consequently, base' + x' generates a contiguous sequence of length modulus'. When evaluated modulo modulus', this sequence produces every integer in [0, modulus' - 1] exactly once.

Thus, the problem transforms into counting how many integers in the range [0, modulus' - 1] are coprime to modulus'. This quantity is mathematically equivalent to Euler's totient function, denoted as φ(modulus').

Algorithm Design

The solution executes two sequential operations per test case:

1. Calculate d using the Euclidean algorithm.
2. Compute φ(modulus / d) via prime factorization. The factorization loop runs up to the square root of the input, yielding a time complexity of O(√N), which efficiently handles values up to 10^{10}.

Reference Implementation

#include <iostream>
#include <numeric>

using ll = long long;

// Iterative Euclidean algorithm
ll calculateGCD(ll a, ll b) {
    while (b) {
        ll remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

// Euler's totient function via trial division
ll computeEulerPhi(ll n) {
    ll totient = n;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) {
                n /= p;
            }
            totient -= totient / p;
        }
    }
    if (n > 1) {
        totient -= totient / n;
    }
    return totient;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    if (!(std::cin >> t)) return 0;

    while (t--) {
        ll startVal, upperBound;
        std::cin >> startVal >> upperBound;
        
        ll sharedFactor = calculateGCD(startVal, upperBound);
        ll reducedModulus = upperBound / sharedFactor;
        
        std::cout << computeEulerPhi(reducedModulus) << '\n';
    }
    return 0;
}