time limit per test: 0.25 sec.
memory limit per test: 4096 KB

For given integer N (1<=N<=10⁴) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

9

Sample Output

6

题意：

问你欧拉函数的值

/*
对于正整数n,在[1,N]中与N互质的正整数个数,记作φ(n)
φ(n) 称为欧拉函数*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=200005;
int prime[maxn],phi[maxn];
bool notprime[maxn];
int main()
{
	int n,cnt=0;
	scanf("%d",&n);
	notprime[1]=true;
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!notprime[i])
		{
			prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(prime[j]*i>n) break;
			notprime[prime[j]*i]=true;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=prime[j]*phi[i];
				break;
			}
			else
				phi[i*prime[j]]=(prime[j]-1)*phi[i];
		}
	}
	cout << phi[n];
	return 0;
}