오일러 피 함수

문제

양의 정수 N이 주어질 때, 오일러 피 함수 φ(N)을 구하여라.

오일러 피 함수 φ(N)은 1 이상 N 이하의 정수 중 N과 서로소인 정수의 개수이다. 두 수가 서로소라는 것은 두 수의 최대공약수가 1이라는 뜻이다.

N의 소인수분해 결과가 $N = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$ 일 때, 오일러 피 함수는 다음과 같이 계산한다.

$\phi(N) = N \times \prod_{p_i | N} (1 - \frac{1}{p_i})$

입력

첫째 줄에 양의 정수 N이 주어진다.

• $1 \le N \le 10^{12}$

출력

첫째 줄에 φ(N)의 값을 출력한다.

예제 입력 1

6

예제 출력 1

2

예제 입력 2

100

예제 출력 2

40