def main():
    n = int(input())
    if n==1:
        print(1)
        return
    ps = []
    i = 2
    x = n
    d = n
    while i*i <= n:
        if x%i==0:
            d = d*(i-1)//i
            ps.append(i)
            while x%i==0:
                x //= i
        i += 1
    if x > 1:
        ps.append(x)
        d = d*(x-1)//x
    divs = []
    i = 1
    while i*i <= d:
        if d%i==0:
            divs.append(i)
            divs.append(d//i)
        i += 1
    divs.sort()
    for x in divs:
        if pow(10, x, n)==1:
            print(x)
            return


if __name__ == "__main__":
    main()