p02470 Euler's Phi Function
For given integer n, count the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n.



Input


n


An integer n (1 ≤ n ≤ 1000000000).

Output

The number of totatives in a line.

Examples

Input

6


Output

2


Input

1000000


Output

400000
```python
# https://tjkendev.github.io/procon-library/python/prime/eulers-totient-function.html
# https://qiita.com/drken/items/a14e9af0ca2d857dad23#%E5%95%8F%E9%A1%8C-6-%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E9%96%A2%E6%95%B0
# オイラー関数
# 1,2,...,NのうちNと互いに素であるものの個数
# Python3 program to calculate 
# Euler's Totient Function 
def euler_phi(n): 
	
	# Initialize result as n 
	result = n; 

	# Consider all prime factors 
	# of n and subtract their 
	# multiples from result 
	p = 2; 
	while(p * p <= n): 
		
		# Check if p is a 
		# prime factor. 
		if (n % p == 0): 
			
			# If yes, then 
			# update n and result 
			while (n % p == 0): 
				n = int(n / p); 
			result -= int(result / p); 
		p += 1; 

	# If n has a prime factor 
	# greater than sqrt(n) 
	# (There can be at-most 
	# one such prime factor) 
	if (n > 1): 
		result -= int(result / n); 
	return result; 


n=int(input())

print(euler_phi(n))


```