Problem:
Problem D:
Identity Function You are given an integer $N$, which is greater than 1. Consider the following functions:  $f(a) = a^N$  mod  $N$  $F_1(a) = f(a)$  $F_{k+1}(a) = F_k(f(a))$ $(k = 1,2,3,...)$  Note that we use mod to represent the integer modulo operation. For a non-negative integer $x$
and a positive integer $y$, $x$ mod $y$ is the remainder of $x$ divided by $y$. Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than
$N$. If no such $k$ exists, output -1. Input The input consists of a single line that contains an integer $N$ ($2 \leq N \leq 10^9$), whose meaning is
described in the problem statement. Output Output the minimum positive integer $k$ such that $F_k(a) = a$ for all positive integers $a$ less than
$N$, or -1 if no such $k$ exists. Sample Input 3 Output for the Sample Input 1 Sample Input 4 Output for the Sample Input -1 Sample Input 15 Output for the Sample Input 2

Solution (Python):
N = int(input())

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
def lcm(m, n):
    return m // gcd(m, n) * n
def carmichael(x):
    r = 1

    b = 0
    while x & 1 == 0:
        b += 1
        x >>= 1
    if b > 1:
        r = 2 if b == 2 else 2**(b-2)

    y = 3
    while y*y <= x:
        if x % y == 0:
            c = 0
            while x % y == 0:
                x //= y
                c += 1
            r = lcm(r, (y-1) * y**(c-1))
        y += 1
    if x > 1:
        r = lcm(r, x-1)
    return r

def solve(x, c):
    if c == 1:
        return 1
    x = x % c
    sq = int(c ** .5) + 1

    mp = {}
    y = 1
    for i in range(sq):
        mp[y] = i
        y = (y * x) % c
        if y == 1:
            return i+1
        if y in mp:
            return -1
    z = 1
    for i in range(sq):
        z = (z * y) % c
        if z in mp:
            return sq*(i+1) - mp[z]
    return -1
c = carmichael(N)
k = solve(N, c)
if k == -1 or pow(N, k, c) != 1 % c:
    print(-1)
else:
    print(k)