1. Abridged Problem Statement
Given an integer N (1 ≤ N ≤ 10⁴), compute how many positive integers ≤ N are coprime with N (i.e. whose gcd with N is 1).

2. Detailed Editorial

Goal: compute φ(N), the number of integers between 1 and N inclusive that are coprime to N.

Two main approaches:

A. Brute-force with gcd
- Iterate i from 1 to N.
- Use Euclid’s algorithm to compute gcd(i, N).
- Increment a counter whenever gcd(i, N) == 1.
- Time complexity: O(N · log N) worst-case, which is fine for N ≤ 10⁴.

B. Euler’s totient formula (more efficient for large N)
- Factorize N into its distinct prime factors: N = p₁^e₁ · p₂^e₂ · … · p_k^e_k.
- Use the formula φ(N) = N · ∏_{i=1..k} (1 – 1/pᵢ).
  - For each prime divisor pᵢ, multiply the running result by (pᵢ – 1)/pᵢ.
- Factorization by trial division up to √N takes O(√N). Totient computation is O(number_of_primes). Overall O(√N), still trivial for N ≤ 10⁴.

The reference solution below takes approach A: with N ≤ 10⁴ the linear scan with gcd is more than fast enough.

Edge case: N = 1 → answer is 1 (only number 1, and gcd(1,1)=1; the loop covers this directly).

3. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;

void read() { cin >> n; }

void solve() {
    // Euler's totient by definition: count how many integers in [1, n] are
    // coprime with n, testing each one with gcd. With n up to 10^4 the linear
    // scan is trivially fast.

    int answer = 0;
    for(int i = 1; i <= n; i++) {
        if(gcd(i, n) == 1) {
            answer++;
        }
    }

    cout << answer << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution
```python
import sys
import math

def main():
    # Read N from stdin, strip newline, convert to integer
    n = int(sys.stdin.readline().strip())

    # Approach A: brute-force gcd
    count = 0
    for i in range(1, n + 1):
        if math.gcd(i, n) == 1:
            count += 1

    # Print the result
    print(count)

if __name__ == "__main__":
    main()
```

Alternative Python: Euler’s totient via factorization
```python
import sys

def compute_phi(n):
    result = n
    x = n
    p = 2
    # Trial divide up to sqrt(x)
    while p * p <= x:
        if x % p == 0:
            # p is a prime divisor
            while x % p == 0:
                x //= p
            # apply totient factor (1 - 1/p)
            result -= result // p
        p += 1 if p == 2 else 2  # increment p (2→3, then skip evens)
    # If remainder x > 1, it's a prime factor
    if x > 1:
        result -= result // x
    return result

def main():
    n = int(sys.stdin.readline())
    print(compute_phi(n))

if __name__ == "__main__":
    main()
```

5. Compressed Editorial
Compute φ(N): either loop i=1..N and count gcd(i,N)==1 in O(N·logN), or factor N in O(√N) and apply φ(N) = N·∏(1–1/p). Both are efficient for N ≤ 10⁴; the reference code uses the simple gcd loop.
