Arthur defines a function, , to be the number of pairs such that:
- and are coprime.
Given an integer, , help Arthur find and print the result of:
Input Format
The first line contains a single integer denoting .
Constraints
Subtasks
- for of the maximum score.
- for of the maximum score.
Output Format
Print the result of on a new line.
Sample Input
12
Sample Output
3
Explanation
The value of for is:
- For , there is only valid pair, , so .
- For , there is only valid pair, , so
- For , there is only valid pair, , so
- For all other , the function returns .
Thus, our final sum is the result of .