def prime_f(num):
    divisors={}
    i=2
    while(i <= num):
        k=0
        while(num % i == 0):
            k+=1
            num //= i
        if k != 0:
            divisors[i]=k
        i += 1
    return divisors
def totient_n(num):
    phi=num
    for i in prime_f(num).keys():
        phi*=(1-1/i)
    return int(phi)
n = int(input())
N = n
n = totient_n(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()