A cryptographic key setup picks two distinct labels i and j from 1..n and only accepts the pair when they share no common factor greater than 1. Count how many unordered pairs (i, j) with 1 <= i < j <= n satisfy gcd(i, j) = 1.
Input format
A single line with one integer n.
Output format
A single integer: the number of coprime pairs (i, j) with 1 <= i < j <= n.
Constraints
- 1 <= n <= 1000000