The cows have just learned what a primitive root is! Given a prime p, a primitive root $\operatorname{mod} p$ is an integer x (1 ≤ x < p) such that none of integers x - 1, x^2 - 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 $\operatorname{mod} p$.


-----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 $\operatorname{mod} p$.


-----Examples-----
Input
3

Output
1

Input
5

Output
2



-----Note-----

The only primitive root $\operatorname{mod} 3$ is 2.

The primitive roots $\operatorname{mod} 5$ are 2 and 3.

Difficulty: interview

Starter code:

Solutions:
x=int(input())
if(x==2):
    print(1)
else:
    x-=1
    cnt=0
    for i in range(1,x):
        ok=0
        for j in range(2,i+1):
            if(x%j==0 and i%j==0): ok=1
        if(ok==0) :cnt+=1
    print(cnt)


p = int(input())

def f(x, p):
    y = 1
    for i in range(p - 2):
        y = (y * x) % p
        if y == 1: return False
    return (y * x) % p == 1

print(sum(f(x, p) for x in range(1, p)))

def phi(n):
    t, i = n, 2
    while i * i <= n:
        if n % i == 0:
            n //= i
            while n % i == 0: n //= i
            t -= t // i
        i += 1
    return t - t // n if n > 1 else t
print(phi(int(input()) - 1))

import sys
import fractions

def phi(n):
    amount = 0

    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1

    return amount

def solve():
    p = int(input())
    return phi(p-1)
    
def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    if isinstance(s, tuple): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")
def run():
    # if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
    res = solve()
    write(res)
run()

import sys
import fractions

def phi(n):
    amount = 0

    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1

    return amount

def solve():
    p = int(input())
    return phi(p-1)
    
def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs  # String
    if mode == 1: return inputs.split()  # List of strings
    if mode == 2: return list(map(int, inputs.split()))  # List of integers
def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    if isinstance(s, tuple): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")
def run():
    # if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
    res = solve()
    write(res)
run()

t=0
from fractions import gcd

x=int(input())-1
for i in range(1, x+1):
     if gcd(x, i)==1:
          t+=1
print(t)


from fractions import gcd
tt=0
#phi(p-1)
x=int(input())
x-=1
for i in range(1, x+1):
    if gcd(x,i)==1:
        tt+=1
print(tt)


from pprint import pprint

def fatoresPrimos(x):
	fatores = {}

	if (x in primeSet):
		fatores[x] = 1
		return fatores

	i = 0
	atual = x
	while (primes[i] < x):
		p = primes[i]
		if (atual % p == 0):
			atual = atual / p
			if (p in fatores):
				fatores[p] += 1
			else:
				fatores[p] = 1
		else:
			i += 1

	return fatores

def phi(x):

	f = fatoresPrimos(x)

	res = 1

	for i in list(f.keys()):
		res *= i ** f[i] * (1 - 1 / i)

	return int(res)



p = int(input())

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003]
primeSet = set(primes)
n = len(primes)

print(phi(phi(p)))


def fatoresPrimos(x):
	fatores = {}

	if (x in primeSet):
		fatores[x] = 1
		return fatores

	i = 0
	atual = x
	while (primes[i] < x):
		p = primes[i]
		if (atual % p == 0):
			atual = atual / p
			if (p in fatores):
				fatores[p] += 1
			else:
				fatores[p] = 1
		else:
			i += 1

	return fatores

def phi(x):

	f = fatoresPrimos(x)

	res = 1

	for i in list(f.keys()):
		res *= i ** f[i] * (1 - 1 / i)

	return int(res)



p = int(input())

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003]
primeSet = set(primes)
n = len(primes)

print(phi(phi(p)))


def main():
    p = int(input())
    if p < 5:
        print(1 )
        return
    res, r = 0, list(range(p - 2))
    for x in range(2, p):
        xx = x
        for _ in r:
            xx %= p
            if xx == 1:
                break
            xx *= x
        else:
            if xx % p == 1:
                res += 1
    print(res)


def __starting_point():
    main()

__starting_point()

p = int(input()) - 1
def hcf(a, b):
    if a is 0:
        return b
    else:
        return hcf(b % a, a)
cnt = 0
for i in range(1, p + 1):
    if hcf(i, p) is 1:
        cnt += 1
print(cnt)


import math
sol = 0
p=int(input())
for e in range(1, p):
     if math.gcd(p-1, e) == 1:
          sol+=1
print(sol)

n=int(input())
if(n==2):
    print(1)
    return
n-=1
res=0
for i in range(1,n):
    chk=True
    for j in range(2,i+1):
        if(n%j==0 and i%j==0): 
            chk=False
    if(chk):
        res+=1
print(res)

p = int(input())

ans = 0

for i in range(1, p):
	t = 1
	for j in range(1, p - 1):
		t = t * i % p
		if (t - 1) % p == 0:
			break
	else:
		t = t * i % p
		if (t - 1) % p == 0:
			ans += 1

print(ans)


def toi(n):
  pre = n - 1
  ans =  1 
  for i in range(2,2000):
    c = 0
    if pre%i==0:
      while pre%i == 0:
        c +=1
        pre//=i
      ans*=(i-1)*(i**(c-1))
    i+=1
  return int(ans)
  
n = int(input())
print(toi(n))

def f(p):
    ans = 0
    for x in range(1, p):
        good = True
        y = x
        for i in range(1, p - 1):
            if y == 1:
                good = False
                break
            y = (y * x) % p
        if y != 1:
            good = False
        if good:
            ans += 1
    return ans

print(f(int(input())))


p=int(input())
if p == 2:
    print(1)
    return
ans=0
for x in range(1,p):
    m=x%p
    if m==1:
        if x==2:
            q=True
        else:
            q=False
    else:
        q=False
        for i in range(2,p):
            m=(m*x)%p
            if m==1:
                if i==p-1:
                    q=True
                break
    ans+=q
print(ans)
    


p=int(input())
if p == 2:
    print(1)
    return
ans=0
for x in range(1,p):
    m=x%p
    if m==1:
        if x==2:
            q=True
        else:
            q=False
    else:
        q=False
        for i in range(2,p):
            m=(m*x)%p
            if m==1:
                if i==p-1:
                    q=True
                break
    ans+=q
print(ans)
    


p=int(input())
count=0
for i in range(1,p):
	z,x=1,1
	for j in range(1,p-1):
		x*=i
		x%=p
		if x==1:
			z=0
			break
	if z==1:
		x*=i
		x%=p
		if x==1:
			count+=1
print(count)
	


# python 3
"""
Modular arithmetic:
This has something to do with Extended Euclidean Algorithm
"""


def cows_and_primitive_roots(p_int):
    if p_int == 2:
        return 1
    count = 0
    for x in range(2, p_int):
        x_to_i_mod_p = x
        divisible = False
        for i in range(2, p_int-1):
            x_to_i_mod_p = (x * x_to_i_mod_p) % p_int
            if x_to_i_mod_p == 1:
                divisible = True
                break
        if not divisible:
            count += 1
            # print(x)

    return count


def __starting_point():
    """
    Inside of this is the test. 
    Outside is the API
    """
    p = int(input())

    print(cows_and_primitive_roots(p))

__starting_point()

from math import gcd

n = int(input().strip())
count = 0
for i in range(1, n):
    if gcd(i, n - 1) == 1:
        count += 1
        #print(i)
print(count)

def prim_roots(number):
    if number == 2:
        return 1
    elif number == 4:
        return 2
    z, h = 1, 2
    p = list()
    while h < number:
        k = pow(h, z, number)
        while k > 1:
            z += 1
            k = (k * h) % number
        if z == number - 1:
            p.append(h)
        z = 1
        h += 1
    return len(p)


print(prim_roots(int(input())))

from fractions import gcd

tt=0

#phi(p-1)

x=int(input())

x-=1

for i in range(1, x+1):

    if gcd(x,i)==1:

        tt+=1

print(tt)



from math import gcd 
p=int(input())-1
cnt=0 
for i in range(1,p):
    if gcd(i,p)==1: cnt+=1 
print(cnt if p!=1 else 1)

p = int(input())
def gcd(a,b): 
      
    # Everything divides 0  
    if (b == 0): 
         return a 
    return gcd(b, a%b) 

c = 0
for i in range(1,p) :
  if gcd(p-1,i) == 1 :
    
    c += 1
    
print(c)