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: MEDIUM
Tags: Mathematics

Number theory

Implementation

Starter code:

Solutions:
from math import gcd
a = int(input()) - 1
aux = 1
for i in range(2, a):
	if gcd(i, a) == 1:
		aux = aux + 1
print(aux)


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return [int(i) for i in input().split()]

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	new_number = 0
	while number > 0:
		new_number += number % base
		number //= base
	return new_number

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
p = ii()
phi = []
for i in range(1, p):
	if math.gcd(i, p) == 1:
		phi.append(i)
phiofphi = len(phi)
r = sieve(phiofphi)
for i in r:
	if phiofphi % i == 0:
		phiofphi = phiofphi * (i - 1) // i
print(int(phiofphi))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
p = int(input())
c = 0
for i in range(1, p):
	if gcd(i, p - 1) == 1:
		c += 1
print(c)


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)


from fractions import gcd
tt = 0
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 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)))


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def main():
	p = int(input())
	ans = 0
	if p == 2:
		print(1)
	else:
		for i in range(2, p):
			temp = 1
			for _ in range(p - 2):
				temp *= i
				temp %= p
				if temp == 1:
					break
			else:
				ans += 1
		print(ans)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


x = int(input())
i = 2
ar = []

def fac(n):
	global i, ar
	if n % i == 0:
		ar.append(i)
		fac(n // i)
	elif i < n:
		i += 1
		fac(n)
fac(x - 1)
c = 1
nar = set(ar)
for i in nar:
	a = len(ar) - ar[::-1].index(i) - (ar.index(i) + 1) + 1
	c = c * i ** (a - 1) * (i - 1)
print(c)


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)


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
	return count

def __starting_point():
	p = int(input())
	print(cows_and_primitive_roots(p))
__starting_point()


n = int(input())
if n == 2:
	print(1)
	exit()
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())
n = p - 1
c = n
i = 2
while n >= i * i:
	if n % i == 0:
		while n % i == 0:
			n = n / i
		c = c / i * (i - 1)
	i = i + 1
if n != 1:
	c = c / n * (n - 1)
print(int(c))


def main():
	p = int(input())
	if p < 5:
		print(1)
		return
	(res, r) = (0, 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)
main()


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))


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)


from math import gcd

def countPrimitiveRoots(p):
	result = 1
	for i in range(2, p, 1):
		if gcd(i, p) == 1:
			result += 1
	return result
p = int(input())
print(countPrimitiveRoots(p - 1))


from math import gcd

def solve(p):
	total = 0
	for i in range(2, p):
		if gcd(i, p) == 1:
			total += 1
	print(total + 1)
n = int(input())
solve(n - 1)


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())))


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(count)


def f(n):
	m = 1
	for i in range(1, p - 1):
		m = m * n % p
		if (m - 1) % p:
			pass
		else:
			return False
	if (m * n - 1) % p:
		return False
	return True
p = int(input())
cnt = 0
for i in range(1, p):
	if f(i):
		cnt += 1
print(cnt)


def phi(n):
	ans = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			ans //= p
			ans *= p - 1
			while n % p == 0:
				n //= p
		p += 1
	if n != 1:
		ans //= n
		ans *= n - 1
	return ans
p = int(input())
print(phi(p - 1))


from math import *
p = int(input())
cnt = 0
c = 0
d = 0
for i in range(1, p):
	if gcd(i, p - 1) == 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)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
c = 0
for i in range(1, n):
	x = i
	t = 1
	for j in range(n - 2):
		if x == 1:
			t = 0
		x = x * i % n
	c += t
print(c)


import math
n = int(input())
ans = 0
for i in range(1, n):
	if math.gcd(i, n - 1) == 1:
		ans += 1
print(ans)


p = int(input())
hash = {2: 1, 3: 1, 5: 2, 7: 2, 11: 4, 13: 4, 17: 8, 19: 6, 23: 10, 29: 12, 31: 8, 37: 12, 41: 16, 43: 12, 47: 22, 53: 24, 59: 28, 61: 16, 67: 20, 71: 24, 73: 24, 79: 24, 83: 40, 89: 40, 97: 32, 101: 40, 103: 32, 107: 52, 109: 36, 113: 48, 127: 36, 131: 48, 137: 64, 139: 44, 149: 72, 151: 40, 157: 48, 163: 54, 167: 82, 173: 84, 179: 88, 181: 48, 191: 72, 193: 64, 197: 84, 199: 60, 211: 48, 223: 72, 227: 112, 229: 72, 233: 112, 239: 96, 241: 64, 251: 100, 257: 128, 263: 130, 269: 132, 271: 72, 277: 88, 281: 96, 283: 92, 293: 144, 307: 96, 311: 120, 313: 96, 317: 156, 331: 80, 337: 96, 347: 172, 349: 112, 353: 160, 359: 178, 367: 120, 373: 120, 379: 108, 383: 190, 389: 192, 397: 120, 401: 160, 409: 128, 419: 180, 421: 96, 431: 168, 433: 144, 439: 144, 443: 192, 449: 192, 457: 144, 461: 176, 463: 120, 467: 232, 479: 238, 487: 162, 491: 168, 499: 164, 503: 250, 509: 252, 521: 192, 523: 168, 541: 144, 547: 144, 557: 276, 563: 280, 569: 280, 571: 144, 577: 192, 587: 292, 593: 288, 599: 264, 601: 160, 607: 200, 613: 192, 617: 240, 619: 204, 631: 144, 641: 256, 643: 212, 647: 288, 653: 324, 659: 276, 661: 160, 673: 192, 677: 312, 683: 300, 691: 176, 701: 240, 709: 232, 719: 358, 727: 220, 733: 240, 739: 240, 743: 312, 751: 200, 757: 216, 761: 288, 769: 256, 773: 384, 787: 260, 797: 396, 809: 400, 811: 216, 821: 320, 823: 272, 827: 348, 829: 264, 839: 418, 853: 280, 857: 424, 859: 240, 863: 430, 877: 288, 881: 320, 883: 252, 887: 442, 907: 300, 911: 288, 919: 288, 929: 448, 937: 288, 941: 368, 947: 420, 953: 384, 967: 264, 971: 384, 977: 480, 983: 490, 991: 240, 997: 328, 1009: 288, 1013: 440, 1019: 508, 1021: 256, 1031: 408, 1033: 336, 1039: 344, 1049: 520, 1051: 240, 1061: 416, 1063: 348, 1069: 352, 1087: 360, 1091: 432, 1093: 288, 1097: 544, 1103: 504, 1109: 552, 1117: 360, 1123: 320, 1129: 368, 1151: 440, 1153: 384, 1163: 492, 1171: 288, 1181: 464, 1187: 592, 1193: 592, 1201: 320, 1213: 400, 1217: 576, 1223: 552, 1229: 612, 1231: 320, 1237: 408, 1249: 384, 1259: 576, 1277: 560, 1279: 420, 1283: 640, 1289: 528, 1291: 336, 1297: 432, 1301: 480, 1303: 360, 1307: 652, 1319: 658, 1321: 320, 1327: 384, 1361: 512, 1367: 682, 1373: 588, 1381: 352, 1399: 464, 1409: 640, 1423: 468, 1427: 660, 1429: 384, 1433: 712, 1439: 718, 1447: 480, 1451: 560, 1453: 440, 1459: 486, 1471: 336, 1481: 576, 1483: 432, 1487: 742, 1489: 480, 1493: 744, 1499: 636, 1511: 600, 1523: 760, 1531: 384, 1543: 512, 1549: 504, 1553: 768, 1559: 720, 1567: 504, 1571: 624, 1579: 524, 1583: 672, 1597: 432, 1601: 640, 1607: 720, 1609: 528, 1613: 720, 1619: 808, 1621: 432, 1627: 540, 1637: 816, 1657: 528, 1663: 552, 1667: 672, 1669: 552, 1693: 552, 1697: 832, 1699: 564, 1709: 720, 1721: 672, 1723: 480, 1733: 864, 1741: 448, 1747: 576, 1753: 576, 1759: 584, 1777: 576, 1783: 540, 1787: 828, 1789: 592, 1801: 480, 1811: 720, 1823: 910, 1831: 480, 1847: 840, 1861: 480, 1867: 620, 1871: 640, 1873: 576, 1877: 792, 1879: 624, 1889: 928, 1901: 720, 1907: 952, 1913: 952, 1931: 768, 1933: 528, 1949: 972, 1951: 480, 1973: 896, 1979: 924, 1987: 660, 1993: 656, 1997: 996, 1999: 648}
print(hash[p])


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
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

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():
	res = solve()
	write(res)
run()


import sys
import collections
from collections import Counter, deque
import itertools
import math
import timeit
import random

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
p = ii()
ans = 0
for i in range(1, p, 1):
	if all((pow(i, j, p) != 1 for j in range(1, p - 1, 1))) and pow(i, p - 1, p) == 1:
		ans += 1
print(ans)


def is_primitive(x, p):
	return pow(x, p - 1, p) == 1 and all((pow(x, e, p) != 1 for e in range(1, p - 1)))
p = int(input())
ans = sum((is_primitive(x, p) for x in range(1, p)))
print(ans)


from functools import *
from operator import *

def count_primitive(n):
	count = 0
	if n == 2:
		return 1
	for i in range(2, n):
		(flag, cur) = (1, i)
		for j in range(1, n - 2):
			cur = cur * i % n
			if cur == 1:
				flag = 0
				break
		if flag and cur * i % n == 1:
			count += 1
	return count
print(count_primitive(int(input())))


from math import sqrt

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)
n = int(input())
print(phi(n - 1))


def __gcd(a, b):
	if b == 0:
		return a
	else:
		return __gcd(b, a % b)
n = int(input())
r = 1
n = n - 1
for i in range(2, n):
	if __gcd(i, n) == 1:
		r += 1
print(r)


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 isPrimitiveRoot(x, p):
	i = 2
	m = phi = p - 1
	while i * i <= m:
		if m % i == 0:
			if pow(x, phi // i, p) == 1:
				return 0
			while m % i == 0:
				m //= i
		i += 1
	if m > 1:
		return pow(x, phi // m, p) != 1
	return pow(x, phi, p) == 1
p = int(input())
ans = 0
for g in range(1, p):
	if isPrimitiveRoot(g, p):
		ans += 1
print(ans)


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p + p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	n = int(input())
	print(phi(n - 1))
for _ in range(1):
	solve()


t = int(input())
import math
res = 0
for i in range(1, t - 1):
	if math.gcd(i, t - 1) == 1:
		res += 1
print(max(1, res))


p = int(input())

def is_primitive(num):
	global p
	np = num % p
	for z in range(1, p - 1):
		if (np - 1) % p == 0:
			return False
		np *= num
		np %= p
	return (np - 1) % p == 0
ct = 0
for i in range(1, p):
	if is_primitive(i):
		ct += 1
print(ct)


import math
p = int(input())
c = 1
for i in range(3, p - 1):
	if math.gcd(i, p - 1) == 1:
		c += 1
print(c)


n = int(input())
r = 0
for i in range(1, n):
	flg = True
	c = 1
	for j in range(1, n - 1):
		c = c * i % n
		if c == 1:
			flg = False
			break
	c = c * i % n
	if c != 1:
		flg = False
	r += 1 if flg else 0
print(r)


from math import *

def count_primitive(n):
	count = 0
	for i in range(1, n):
		if gcd(i, n - 1) == 1:
			count += 1
	return count
print(count_primitive(int(input())))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from math import sqrt, floor, factorial, gcd
from collections import deque, Counter, defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from collections import deque
input = lambda : sys.stdin.readline().rstrip('\r\n')
read = lambda : list(map(int, input().strip().split(' ')))

def prim_root(n, p):
	for i in range(1, p - 1):
		if (pow(n, i, p) - 1) % p == 0:
			return False
	return True

def solve():
	n = int(input())
	ans = 0
	for i in range(1, n):
		ans += prim_root(i, n)
	print(ans)
solve()


n = int(input())
ro = 0
for i in range(2, n):
	c = 1
	for h in range(1, n):
		c = c * i % n
		if c % n == 1:
			if h == n - 1:
				ro += 1
			else:
				break
print(ro + (n == 2))


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)


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)


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)


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 math import gcd
n = int(input())
result = 1
for i in range(2, n - 1):
	if gcd(i, n - 1) == 1:
		result += 1
print(result)


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


import sys
import math
import itertools
import functools
import collections
import operator

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)
p = ii()
ans = 0
for i in range(1, p, 1):
	t = ''
	for j in range(1, p - 1, 1):
		if pow(i, j, p) != 1:
			t += '0'
		else:
			break
	if pow(i, p - 1, p) == 1:
		t += '1'
	if t == '0' * (p - 2) + '1':
		ans += 1
print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
count = []
count = [1 if gcd(i, n - 1) == 1 else 0 for i in range(1, n)]
print(sum(count))


p = int(input())
n = p - 1
prime_factors = {}
while n % 2 == 0:
	n >>= 1
	prime_factors[2] = prime_factors.get(2, 0) + 1
for i in range(3, int(n ** (1 / 2)) + 1, 2):
	if n % i == 0:
		while n % i == 0:
			n //= i
			prime_factors[i] = prime_factors.get(i, 0) + 1
if n > 2:
	prime_factors[n] = 1
n = p - 1
total = 1
for (i, j) in prime_factors.items():
	total *= i ** (j - 1) * (i - 1)
print(total)


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))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def solve():
	p = inp()
	count = 0
	for i in range(1, p):
		cur = i
		found = False
		for j in range(p - 2):
			if (cur - 1) % p == 0:
				found = True
			cur *= i
			cur %= p
		if not found and (cur - 1) % p == 0:
			count += 1
	print(count)

def main():
	t = 1
	for i in range(t):
		solve()
BUFSIZE = 8192

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		to = f(*args, **kwargs)
		if stack:
			return to
		else:
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						return to
					to = stack[-1].send(to)
	return wrappedfunc

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math
p = int(input())
c = 0
for i in range(1, p):
	f = 0
	for j in range(1, p - 1):
		if pow(i, j, p) == 1:
			f = 1
			break
	if f == 0 and pow(i, p - 1, p) == 1:
		c += 1
print(c)


import sys
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result
mod = 1000000007

def pow(a, ex):
	if ex == 0:
		return 1
	if ex % 2 == 0:
		return pow(a % mod * (a % mod) % mod, int(ex / 2))
	else:
		return a * pow(a % mod * (a % mod) % mod, int(ex / 2)) % mod

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	tt = 0
	x = int(input())
	x -= 1
	for i in range(1, x + 1):
		if gcd(x, i) == 1:
			tt += 1
	print(tt)
main()


import math
r = 1
x = int(input())
for i in range(2, x - 1):
	if math.gcd(i, x - 1) == 1:
		r += 1
print(r)


from math import gcd
p = int(input()) - 1
ans = 0
for j in range(1, p + 1):
	if gcd(j, p) == 1:
		ans += 1
print(ans)


p = int(input())
ans = 0
for i in range(1, p):
	result = True
	temp = i
	for j in range(1, p):
		if j == p - 1:
			if (temp - 1) % p != 0:
				result = False
		elif (temp - 1) % p == 0:
			result = False
			break
		temp *= i
		temp %= p
	if result:
		ans += 1
print(ans)