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.
#!/usr/bin/env python3
from math import sqrt
def isPrime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    vmax = int(sqrt(n))
    for i in range(2,vmax+1):
        if(n%vmax==0):
            return False
    return True

if __name__ == "__main__":
    p = int(input())
   
    res = 0
    if not isPrime(p):
        print(0)
    else:
        for x in range(1,p):
            ok = True
            num = 1
            #print('x = %d'%x)
            for i in range(1,p-1):
                num = (num*x)%p
                n = num-1
                #print('divide = %d'%n)
                if n  == 0:
                    ok = False
                    break
            if ok == True:
                num = (num*x)%p
                n = num -1
                #print('divide = %d'%n)
                if n == 0:
                    res += 1
                    #print(x)

        print(res)


