def euler_phi(n):
    res = n
    x = 2
    while x*x <= n:
        if n % x == 0:
            res = res // x * (x-1)
            while n % x == 0:
                n //= x
        x += 1
    if n > 1:
        res = res // n * (n-1)
    return res

n = int(input())
N = n
n = euler_phi(n)
C = set()
for i in range(1, int(n**(1/2))+1):
    if n % i == 0:
        C.add(i)
        C.add(n//i)

C = list(C)
C.sort()
for c in C:
    if pow(10, c, N) == 1:
        print(c)
        exit()