<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

102. Coprimes

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


For given integer N (1<=N<=104) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).


Input

Input file contains integer N.


Output

Write answer in output file.


Sample Input

9
Sample Output

6

<|response|>
1. Abridged Problem Statement
Given a positive integer N (1 ≤ N ≤ 10 000), compute how many integers i in the range [1..N] satisfy gcd(i, N) = 1.

2. Key Observations
- The quantity we want is exactly Euler’s totient function φ(N).
- Definition: φ(N) is the count of integers from 1 to N that are coprime with N.
- Two common ways to compute φ(N):
  a. Brute-force gcd: for each i from 1 to N compute gcd(i, N) and count how many times it equals 1. Runs in O(N·log N), fast enough for N ≤ 10⁴.
  b. Using the formula φ(N) = N · ∏_{p | N} (1 – 1/p), where the product runs over the distinct prime divisors p of N. Factorizing N by trial division up to √N takes O(√N).
- Because N is at most 10⁴, the brute-force gcd loop is the simplest correct choice and is what the reference code uses.

3. Full Solution Approach
Step 1. Read N.
Step 2. Initialize a counter to 0.
Step 3. For each i from 1 to N, compute gcd(i, N) with Euclid’s algorithm; if it equals 1, increment the counter. This also handles N = 1 correctly, since gcd(1, 1) = 1.
Step 4. Print the counter, which equals φ(N).

This runs in O(N·log N), which is more than fast enough for N ≤ 10⁴.

4. C++ Implementation
```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;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
import math

def main():
    data = sys.stdin.readline().strip()
    if not data:
        return
    n = int(data)

    # Brute-force: count i in [1..n] with gcd(i, n) == 1.
    # This handles n = 1 correctly since gcd(1, 1) == 1.
    count = 0
    for i in range(1, n + 1):
        if math.gcd(i, n) == 1:
            count += 1

    print(count)

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

Explanation of the main steps:
- We directly apply the definition of φ(N): the number of integers in [1..N] coprime with N.
- For each candidate i, Euclid’s gcd decides coprimality in O(log N).
- With N ≤ 10⁴ the overall O(N·log N) work is negligible, so no factorization is needed.
