The cows have just learned what a primitive root is! Given a prime *p*, a primitive root <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/> is an integer *x* (1 ≤ *x* &lt; *p*) such that none of integers *x* - 1, *x*<sup class="upper-index">2</sup> - 1, ..., *x*<sup class="upper-index">*p* - 2</sup> - 1 are divisible by *p*, but *x*<sup class="upper-index">*p* - 1</sup> - 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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The input contains a single line containing an integer *p* (2 ≤ *p* &lt; 2000). It is guaranteed that *p* is a prime.
import math

p=int(input())
p-=1
num=p
factors=[]
count=[]
while num % 2 == 0:
    if 2 not in factors:
        factors.append(2)
        count.append(1)
    else:
        count[0]+=1
    num = num / 2
for i in range(3, int(math.sqrt(num)) + 1, 2):
    while num % i == 0:
        if i not in factors:
            factors.append(i)
            count.append(1)
        else:
            k=factors.index(i)
            count[k]+=1
        num = num / i
if num > 2:
    factors.append(num)
    count.append(1)
ans=int(p)
for i in factors:
    ans*=(i-1)/i
print(int(ans))