CodeEff/ECCO huggingface dataset:
# Original solution
import sys

N = int(sys.stdin.readline().strip())

def factorization(n):
    arr = []
    temp = n
    # sqrtまで
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    """
    if arr == []:
        arr.append([n, 1])
    """
    return arr

# 素因数とその出現回数
factors = {}
for i in range(1, N+1):
    tmp = factorization(i)
    # print(tmp)
    for factor, count in tmp:
        if factor not in factors:
            factors[factor] = 0
        factors[factor] += count
# print(factors)

ans = 1
for factor, count in list(factors.items()):
    ans *= (count + 1)
    ans %= 10**9 + 7

print(ans)

# Optimized solution
import sys

N = int(sys.stdin.readline())
mod = 10**9 + 7

values = [i for i in range(N+1)]
factors = {}
exists = set()
for i in range(2, N+1):
    if i not in factors:
        factors[i] = 0
    for j in range(i, N+1, i):
        tmp = values[j]
        while tmp % i == 0:
            factors[i] += 1
            tmp //= i
        values[j] = tmp

# print(values)
# print(factors)
ans = 1
for factor, count in list(factors.items()):
    ans *= count + 1
    ans %= mod

print(ans)
# Original solution
#!/usr/bin/env python3
n = int(eval(input()))
def count(x):
    c = 0
    t = n
    while t:
        c += t//x
        t //= x
    return c +1
prime = [2]
limit = int(n**0.5)
ans = count(2)
if n < 3:
    print(ans)
    exit()
data = [i + 1 for i in range(2, n, 2)]
while True:
    p = data[0]
    if limit < p:
        for i in data:
            ans *= count(i)
            ans %= 10**9+7
        break
    ans *= count(p)
    ans %= 10**9 + 7
    data = [e for e in data if e % p != 0]
print(ans)


# Optimized solution
#!/usr/bin/env python3
n = int(eval(input()))
def count(x):
    c = 0
    t = n
    while t:
        c += t//x
        t //= x
    return c +1
limit = int(n**0.5)
ans = count(2)
if n < 3:
    print(ans)
    exit()
data = [i + 1 for i in range(2, n, 2)]
while data:
    p = data[0]
    ans *= count(p)
    ans %= 10**9 + 7
    data = [e for e in data if e % p != 0]
print(ans)
# Original solution
import math
import collections
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
            
    return primes
p = primes(10000)
dic = collections.defaultdict(int)
N = int(eval(input()))
mod = 10**9 +7
for i in range(1, N+1):
    for j in p:
        while i % j == 0:
            dic[j] += 1
            i = i // j
    ans = 1
for c in list(dic.values()):
    ans *= (c+1)
    ans %= mod
print(ans)
                

# Optimized solution
import math
import collections

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

p = primes(1000)
dic = collections.defaultdict(int)
N = int(eval(input()))
mod = 10**9 +7
for i in range(1, N+1):
    for j in p:
        while i % j == 0:
            dic[j] += 1
            i = i // j
    ans = 1
for c in list(dic.values()):
    ans *= (c+1)
    ans %= mod
print(ans)
# Original solution
from collections import defaultdict

MOD = 1000000007


def prime_generator(limit):
    yield 2
    n, h = 3, {}
    while n <= limit:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


def solve(n):
    ps = list(prime_generator(n))
    prev = defaultdict(int)
    for i in range(1, n):
        f = prev.copy()
        k = i + 1
        for p in ps:
            while k % p == 0:
                k //= p
                f[p] += 1
            if k == 1:
                break
        prev = f

    ans = 1
    for c in list(prev.values()):
        ans *= c + 1
        ans %= MOD
    return ans


print((solve(int(eval(input())))))


# Optimized solution
from collections import defaultdict

MOD = 1000000007


def prime_generator(limit):
    yield 2
    n, h = 3, {}
    while n <= limit:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


def solve(n):
    ps = list(prime_generator(n))
    factors = defaultdict(int)
    for i in range(1, n):
        k = i + 1
        for p in ps:
            while k % p == 0:
                k //= p
                factors[p] += 1
            if k == 1:
                break

    ans = 1
    for c in list(factors.values()):
        ans *= c + 1
        ans %= MOD
    return ans


print((solve(int(eval(input())))))
# Original solution
N = int(eval(input()))
m = pow(10,9)+7

A = [1]*(N+1)
for n in range(2,N+1):
    k = n
    for i in range(2,n+1):
        if k%i==0:
            while k>1:
                k//=i
                A[i]+=1
                if k%i!=0:break
ans = 1
for a in A:ans*=a
print((ans%m))

# Optimized solution
N = int(eval(input()))
mod = pow(10,9)+7
A = [1]*(N+1)
for i in range(1,N+1):
    n = i
    for j in range(2,i+1):
        if j>n:break
        while n%j==0:
            A[j]+=1
            n//=j
cnt = 1
for i in range(N+1):
    cnt *= A[i]
print((cnt%mod))
# Original solution
from math import factorial
n = int(eval(input()))
m = factorial(n)
s = 2
ans = 1
while m != 1:
    c = 1
    while m % s == 0:
        c += 1
        m = m // s
    ans *= c
    s += 1
print((ans % (10**9+7)))

# Optimized solution
from math import factorial
n = int(eval(input()))
m = factorial(n)
s = 2
ans = 1
while m > 1:
    c = 1
    while m % s == 0:
        c += 1
        m = m // s
    ans *= c
    s += 1
print((ans % (10**9+7)))
# Original solution
MOD = 10 ** 9 + 7
n = int(eval(input()))

res = 1
ex = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(2, i + 1):
        if i % j == 0:
            while i % j == 0:
                ex[j] += 1
                i //= j

ans = 1
for i in range(n + 1):
    ans *= (ex[i] + 1)
    ans %= MOD
    
print(ans)


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])

    return res


def resolve():
    n = int(eval(input()))

    P = [0] * 1000
    for i in range(1, n + 1):
        t = prime_factorization(i)
        for num, ex in t:
            P[num] += ex

    res = 1
    for p in P:
        res *= p + 1
        res % mod

    print((res % mod))


if __name__ == '__main__':
    resolve()
# Original solution
a = [True] * 1001
a[0] = False
a[1] = False
b = []
c = {}
for i in range(2, 1001):
    if a[i]:
        b.append(i)
        for j in range(2, 1001, 2):
            a[j] = False
d = int(eval(input()))
for j in range(2, d + 1):
    temp_j = j
    for i in b:
        while True:
            if temp_j % i != 0:
                break
            else:
                if i not in c:
                    c[i] = 1
                else:
                    c[i] += 1
                temp_j //= i
e = 1
for k in list(c.keys()):
    e = (e * (c[k] + 1)) % (10 ** 9 + 7)
print(e)


# Optimized solution
z = int(eval(input()))
a = [True] * 1001
a[0] = False
a[1] = False
b = []
for i in range(2, 1001):
    if a[i]:
        b.append(i)
        for j in range(i, 1001, i):
            a[j] = False
c = {}
for i in range(1, z + 1):
    d = i
    while True:
        if d == 1:
            break
        else:
            while d != 1:
                for j in b:
                    if d % j == 0:
                        d //= j
                        if j not in c:
                            c[j] = 1
                        else:
                            c[j] += 1
e = 1
for v in list(c.values()):
    e = (e * (v + 1)) % (10 ** 9 + 7)
print(e)
# Original solution
import collections
def e(N):
    res = []
    x = N
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1:
        res.append(x)
    return res
MOD = 10**9 + 7
n = int(eval(input()))
chk = [0 for i in range(n+1)]
for i in range(2, n+1):
    tmp = collections.Counter(e(i))
    for j in tmp:
        chk[j] += tmp[j]
ans = 1
for i in chk:
    if i:
        ans = ans*(i + 1)%MOD
print(ans)

# Optimized solution
MOD = 10**9 + 7
n = int(eval(input()))
chk = [0 for i in range(n+1)]
for i in range(2, n+1):
    y = 2
    while y*y <= i:
        while i % y == 0:
            chk[y] += 1
            i //= y
        y += 1
    if i > 1:
        chk[i] += 1

ans = 1
for i in chk:
    if i:
        ans = ans*(i + 1)%MOD
print(ans)
# Original solution
n=int(eval(input()));a=1;r=range
for x in[i for i in r(2,n+1)if all(i%j for j in r(2,i))]:a*=sum(n//x**i for i in r(1,11))+1
print((a%(10**9+7)))

# Optimized solution
n=int(eval(input()));a=1;r=range
for x in[i for i in r(2,n+1)if all(i%j for j in r(2,int(i**.5)+1))]:a*=sum(n//x**i for i in r(1,11))+1;a%=10**9+7
print(a)
# Original solution
import math

N = int(eval(input()))

ans=1
x = math.factorial(N)
for i in range(1, x//2+1):
    if x%i == 0:
        ans += 1
print((ans%(10**9+7)))

# Optimized solution
import math

N = int(eval(input()))
x = math.factorial(N)

ans = 1
i = 2
while i <= x:
    cnt = 1
    while x%i == 0:
        x //= i
        cnt += 1
    ans *= cnt
    i += 1
                
print((ans%(10**9+7)))
# Original solution
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

import math
N = int(eval(input()))
l = math.factorial(N)
t = make_divisors(l)
print((len(t)%(10**9+7)))


# Optimized solution
N= int(eval(input()))

m = 10**9+7
pri_num = [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]
dic = {}

for i in range(2,N+1):
    for pri in pri_num:
        while i>0:
            if i % pri == 0:
                if pri in dic:
                    dic[pri] +=1
                else:
                    dic[pri]=1
                i = i//pri

            else:
                break

count = 1
for val in list(dic.values()):
    count = (count*(val+1))%m
print(count)
# Original solution
N= int(eval(input()))

m = 10**9+7
pri_num = [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]
dic = {}

for i in range(2,N+1):
    for pri in pri_num:
        while i>0:
            if i % pri == 0:
                if pri in dic:
                    dic[pri] +=1
                else:
                    dic[pri]=1
                i = i//pri

            else:
                break

count = 1
for val in list(dic.values()):
    count = (count*(val+1))%m
print(count)

            


# Optimized solution
def prime_number(n):
    lis= []
    for i in range(2,n+1):
        j = 2
        flag = 0
        
        while j*j <= i:
            if i%j ==0:
                flag = 1
                break
            else:
                j +=1
        if flag ==0:
            lis.append(i)
    return lis



N= int(eval(input()))
m = 10**9+7
pri_num = prime_number(N)
dic = {}

for i in range(2,N+1):
    for pri in pri_num:
        while i>0:
            if i % pri == 0:
                if pri in dic:
                    dic[pri] +=1
                else:
                    dic[pri]=1
                i = i//pri

            else:
                break

count = 1
for val in list(dic.values()):
    count = (count*(val+1))%m
print(count)
# Original solution
import math
mod = 10 ** 9 + 7

def f(num):

    i = 2
    d = dict()

    while i * i <= num:
        if num % i == 0:
            num //= i
            d[i] = d.get(i, 0) + 1
        else:
            i += 1
    d[num] = 1

    return d

n = int(eval(input()))
if n == 1:
    print((1))
    exit()

ans = 1

for i in list(f(math.factorial(n)).values()):
    ans *= i+1

print((ans%mod))

# Optimized solution
import math
mod = 10 ** 9 + 7

def f(num):
    i = 2
    d = dict()
    while i ** 2 <= num:
        if num % i == 0:
            num //= i
            d[i] = d.get(i, 0) + 1
        else:
            i += 1
    d[num] = 1
    return d

n = int(eval(input()))

if n == 1:
    print((1))
    exit()

ans = 1
for i in list(f(math.factorial(n)).values()):
    ans *= i+1

print((ans%mod))
# Original solution
from math import factorial

N = factorial(int(eval(input())))
i = 2
ans = dict()
n = N
while i*i <= N:
    while n%i ==0:
        n = n//i
        if i in ans:
            ans[i] += 1
        else:
            ans[i] = 1
    i += 1
if n != 1:
    ans[n] = 1

cnt = 1
for value in list(ans.values()):
    cnt *= value + 1
M = 10**9 + 7    
print((cnt%M))

# Optimized solution
from math import factorial
N = factorial(int(eval(input())))
mod = 10**9 + 7
ans = 1
i = 2

while i*i <= N:
    cnt = 1
    while N%i == 0:
        cnt += 1
        N //= i
    ans *= cnt
    i += 1

if N != 1:
    ans *= 2
print((int(ans%mod)))
# Original solution
n=int(eval(input()))
k=1
ans=0
for i in range (n):
    k=k*(i+1)
for j in range(k):
    if k%(j+1)==0:
        ans+=1
print((ans%1000000007))


# Optimized solution
n=int(eval(input()))
l=[k for k in range(1,n+1)]
phrase=[]
ans=1
a=1
def prime(x):
    i=2
    while i*i<=x:
        if x%i==0:
            return False
        i+=1
    return True
for i in range(2,n+1):
    if prime(i):
        phrase.append(i)
for j in phrase:
    for m in range(n):
        while l[m]%j==0:
            a+=1
            l[m]=l[m]/j
    ans=ans*a
    a=1
print((ans%1000000007))
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(eval(input()))
MOD = 10 ** 9 + 7

factorial = [0] * (n+1)
factorial[0] = 1
for i in range(1, n+1):
    factorial[i] = factorial[i-1] * i

prime_factors = []
target = factorial[n]
i = 2
while i ** 2 <= target:
    if target % i != 0:
        i += 1
        continue

    ext = 0
    while target % i == 0:
        ext += 1
        target //= i

    prime_factors.append((i, ext))
    i += 1

if target != 1:
    prime_factors.append((target, 1))

ans = 1
for pf in prime_factors:
    ans = (ans * (pf[1] + 1)) % MOD

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(eval(input()))
MOD = 10 ** 9 + 7

factorial = [0] * (n+1)
factorial[0] = 1
for i in range(1, n+1):
    factorial[i] = (factorial[i-1] * i)

n = factorial[n]
prime_factors = []
i = 2
while i ** 2 <= n:
    ext = 0
    while n % i == 0:
        ext += 1
        n //= i
    if ext:
        prime_factors.append((i, ext))
    i += 1
if n != 1:
    prime_factors.append((n, 1))

ans = 1
for pf, num in prime_factors:
    ans = (ans * (num + 1)) % MOD
print(ans)
# Original solution
import math
import collections

N = int(eval(input()))
a = math.factorial(N)
b = []
while a % 2 == 0:
    b.append(2)
    a//=2
f = 3
while f*f <= a:
    if a % f ==0:
        b.append(f)
        a //= f
    else:
        f += 2
if a != 1:
    b.append(a)

c = collections.Counter(b)
ans = 1
for j,k in list(c.items()):
    ans *= (k+1)
print((ans%(10**9+7)))

# Optimized solution
import math
N=math.factorial(int(eval(input())))
i=2
ans=1
M=10**9+7
while i*i<=N:
    cnt=1
    while N%i==0:
        cnt+=1
        N//=i
    ans*=cnt
    i+=1
if N!=1:ans*=2
print((int(ans%M)))
# Original solution
L = list(input().split())
val = 0
for i in range(len(L)-1):
    if L[i][-1]  != L[i+1][0]:
        print("NO")
        quit()
print("YES")


# Optimized solution
L = list(input().split())
val = 0
for i in range(len(L)-1):
    if L[i][-1]  != L[i+1][0]:
        print("NO")
        break
else:
  print("YES")
# Original solution
a,b,c = input().split()
print(('YES' if a[-1]==b[0] and b[-1]==c[0] else 'NO'))


# Optimized solution
a,b,c=list(map(str,input().split()))
print(('YES' if a[-1]==b[0] and b[-1]==c[0] else 'NO'))
# Original solution
A,B,C=input().split()
print(("YES" if A[-1]==B[0]and B[-1]==C[0] else "NO"))

# Optimized solution
A, B, C = input().split()
if A[-1] == B[0] and B[-1] == C[0]:
    print("YES")
else:
    print("NO")
# Original solution
s = input().split()
a, b, c = s[0], s[1], s[2]
if b.startswith(a[-1:]) and c.startswith(b[-1:]):
  print("YES")
else:
  print("NO")

# Optimized solution
a, b, c = input().split()
if a[-1:] == b[:1] and b[-1:] == c[:1]:
  print("YES")
else:
  print("NO")
# Original solution
a, b, c = input().split()
if a[len(a)-1] == b[0] and b[len(b)-1] == c[0]:
  print("YES")
else:
  print("NO")

# Optimized solution
a, b, c = input().split()
print(("YES" if a[-1] == b[0] and b[-1] == c[0] else "NO"))
# Original solution
a,b,c=input().split()
print(("YES" if a[-1]==b[0] and b[-1]==c[0] else "NO"))

# Optimized solution
A, B, C = input().split()
print(("YES" if A[-1] == B[0] and B[-1] == C[0] else "NO"))
# Original solution
A, B, C = input().split()


if A[-1] == B[0] and B[-1] == C[0]:
    print('YES')
else:
    print('NO')


# Optimized solution
A, B, C = input().split()

def answer(A: int, B: int, C: int) -> str:
    if A[-1] == B[0] and B[-1] == C[0]:
        return 'YES'
    else:
        return 'NO'

print((answer(A, B, C)))
# Original solution
a,b,c = input().split(' ')
print(('YES' if a[len(a)-1] == b[0] and b[len(b)-1] == c[0] else 'NO'))

# Optimized solution
a,b,c = input().split(' ')
print(('YES' if a[-1] == b[0] and b[-1] == c[0] else 'NO'))
# Original solution
a,b,c=input().split();print(('YNEOS'[a[::-1][0]!=b[0]or b[::-1][0]!=c[0]::2]))

# Optimized solution
a,b,c=input().split();print(('YNEOS'[a[-1]!=b[0]or b[-1]!=c[0]::2]))
# Original solution
a, b, c = input().split()
if a[-1] == b[0] and b[-1] == c[0]:
  print("YES")
else:
  print("NO")

# Optimized solution
a, b, c = list(map(str, input().split()))
print(("YES" if a[-1] == b[0] and b[-1] == c[0] else "NO"))
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys
import math


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    k = 3
    while k <= math.sqrt(n):
        if not n % k:
            return False
        k += 2

    return True


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print((phi(n1)))

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def soi(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if n % k == 0:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        tmp = soi(n)
        # print(tmp)
        if n == 1:
            break
        while n % tmp == 0:
            n //= tmp
        ans *= (1 - 1 / tmp)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print((phi(n1)))
# Original solution
n=m=int(eval(input()))
i=2
while i<=n and m!=1:
    if m%i==0:
        n=n*(i-1)//i
        while m%i==0: m//=i
    i+=1
print(n)

# Optimized solution
n=m=int(eval(input()))
i=2
while i*i<=n:
    if n%i==0:
        m=m//i*(i-1)
        while n%i==0: n//=i
    i+=1
if n!=1:m=m//n*(n-1)
print(m)
# Original solution
a=int(eval(input()))
li=[0]*10000000
count=1
i=2 # ??????????????°
while i<a:    
    r=0
    ta=a
    b=i
    if li[i]!=1:
        while True:
                    
            r=ta%b
            if r==0:
                break
            ta=b
            b=r
        if b==1:
            count+=1
        else:
            temp=i
            l=2
            while True:
               li[temp*l]=1
               l+=1
               if temp*l>a:
                   break
    i+=1                
print(count)

# Optimized solution
def soi(n): #?´??????°????§£?????¢?????´?????????
    i=2
    while True:
        if i*i>n:
            return n
        
        if n%i==0:
            return i
        i+=1


a=int(eval(input()))
ans=a
count=1
i=2 # ??????????????°
while True:
    temp=soi(a)
    if a==1: #?´??????°??????????????°
        break
    while a%temp==0: #?´??????°??§???????¶???????
        a/=temp
     #   print (a)

    ans*=(1-1/temp)
    #print (ans)

print((int(ans)))


                
       

def gcd(a,b): #?????§??¬?´???°???????????°??????
    r=0
    while True:
       r=a%b
       if r==0:
           break
       a=b
       b=r
    return b
# Original solution
f=lambda x:p*(x-1)//x
p=n=int(eval(input()))
d=2
while d*d<=n:
 if n%d==0:
  p=f(d)
  while n%d==0:n//=d
 d+=1
if n>1:p=f(n)
print(p)


# Optimized solution
p=n=int(eval(input()))
d=2
while d*d<=n:
 if n%d==0:
  p=p*(d-1)//d
  while n%d==0:n//=d
 d+=1
print(([p,p*(n-1)//n][n>1]))
# Original solution
import sys
def gcd(a,b):
    if(b == 0):
        return a
    else:
        c = b
        b = a%b
        a = c
        return(gcd(a,b))

x = int(eval(input()))
count = 0
for y in range(1,x+1):
    if gcd(x,y) == 1:
        count+=1

print(count)

# Optimized solution
import sys
def euler(a):
    i = 2
    res = a
    #standard = a
    while i * i <= a:
        if a % i == 0:
            res = res - res//i
            while a % i == 0:
                a //= i

        i += 1
    if a != 1:
        res = res - res//a

    return res


x = int(eval(input()))


print((euler(x)))