407125: GYM102697 096 Numbers

Numbers

You're working with large numbers, and you want to calculate the totient function of a certain one. The totient function of a number $$$n$$$ is defined as the number of positive integers less than or equal $$$n$$$ that are relatively prime with $$$n$$$, i.e. the number of integers $$$k$$$ such that $$$k$$$ <= $$$n$$$ and $$$gcd(k, n) = 1$$$.

For example, the totient of $$$15$$$ is $$$8$$$, because 1, 2, 4, 7, 8, 11, 13, and 14 are relatively prime with $$$15$$$, while 3, 5, 6, 9, 10, 12, and 15 are not. 4 is relatively prime with 15, because there aren't any common factors of 4 and 15. 4 has factors {2}, and 15 has factors {3, 5}. On the other hand, 10 is not relatively prime with 15, because 10 and 15 both have a common factor of 5.

Given an integer $$$n$$$, figure out the value of $$$φ(n)$$$, where $$$φ$$$ represents the totient function as described above.

The only line of input contains a single positive integer $$$n$$$ less than 1000.

Output a single positive integer $$$p$$$: the value of $$$φ(n)$$$ as described above.

15

8

60

16

7

6