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.
def Power(a,b):
    if(b==0):
        return 1
    else:
        if(b%2==0):
            return Power(a,b//2)*Power(a,b//2)
        else:
            return a*Power(a,(b-1)//2)*Power(a,(b-1)//2)
n=int(input())
ans=[]
for i in range(1,n):
    l=[]
    c=0
    for j in range(1,n):
        l.append(Power(i,j)-1)
    print(l)    
    for j in range(len(l)-1):
        if(l[j]%n==0):
            c=1        
    if(c!=1 and l[len(l)-1]%n==0):
        
        ans.append(i)
print(len(ans))
