A scheduling system assigns time slots numbered 1 through n in a repeating cycle of length n. A slot k is considered 'independent' if gcd(k, n) == 1.
Given n, count how many integers k with 1 <= k <= n are independent (coprime to n). By convention, when n = 1, the only value k = 1 counts (its gcd with 1 is 1).
Input format
Line 1: a single integer n.
Output format
A single integer: the count of k in [1, n] with gcd(k, n) = 1.
Constraints
- 1 <= n <= 1000000