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
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>

using namespace std;

int gcd(int a, int b){
	if(a < b) swap(a,b);
	if(a == 0 || b == 0) return max(a,b);
	else return gcd(b, a % b);
}

int eulerPhi(int n){
	if(n == 0) return 0;
	int ans = n;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0){
			ans -= ans / i;
			while(n % i == 0) n /= i;
		}
	}
	if(n > 1) 
		ans -= ans / n;
	return ans;
}


int main(){
	int n, cnt = 0;
	cin >> n;
	cout << eulerPhi(n) << endl;
	return 0;
}