Cows and Primitive Roots

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The cows have just learned what a primitive root is! Given a prime p, a primitive root is an integer x (1 ≤ x < p) such that none of integers x - 1, x² - 1, ..., x^p - 2 - 1 are divisible by p, but x^p - 1 - 1 is.

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime p, help the cows find the number of primitive roots .

Input

The input contains a single line containing an integer p (2 ≤ p < 2000). It is guaranteed that p is a prime.

Output

Output on a single line the number of primitive roots .

Sample test(s)

Input

3

Output

1

Input

5

Output

2

Note

The only primitive root is 2.

The primitive roots are 2 and 3.

可使用蛮力法，但需要注意两点：

1、不要每次都用pow计算x的n次方，由于x^n=x*X^(n-1)，设一个变量m储存x^(n-1)，那么x^n=m*x.

2、如果直接算出m，就算用64位也会溢出，利用性质（a-b）%p=(a%p-b%p)%p，则只需保留m%p的值。

AC Code：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include