Example

Input

3


Output

1
#include <iostream>
#include <algorithm>

template <class T>
T gcd(T n, T m) {
    if (n < 0) n = -n;
    if (m < 0) m = -m;
    while (m != 0) {
        n %= m;
        std::swap(n, m);
    }
    return n;
}

using lint = long long;

lint pow(lint b, lint n, lint m) {
    lint x = 1;
    b %= m;

    while (n > 0) {
        if (n & 1) (x *= b) %= m;
        n >>= 1;
        (b *= b) %= m;
    }
    return x;
}

lint totient(lint n) {
    lint m = n;

    for (lint p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;

        m = m / p * (p - 1);
        while (n % p == 0) n /= p;
    }

    if (n > 1) m = m / n * (n - 1);

    return m;
}

void solve() {
    lint n;
    std::cin >> n;

    lint l = 1;
    {
        auto nn = n;
        for (lint p = 2; p * p <= nn; ++p) {
            if (nn % p != 0) continue;

            l *= (p - 1) / gcd(l, p - 1);

            if (nn % (p * p) == 0) {
                std::cout << -1 << std::endl;
                return;
            }
            nn /= p;
        }

        if (nn > 1) {
            auto p = nn;
            l *= (p - 1) / gcd(l, p - 1);
        }
    }

    if (gcd(n, l) != 1) {
        std::cout << -1 << std::endl;
        return;
    }

    auto m = totient(l);

    auto ans = m;
    for (lint p = 1; p * p <= m; ++p) {
        if (m % p != 0) continue;

        if (pow(n, p, l) == 1) ans = std::min(ans, p);
        if (pow(n, m / p, l) == 1) ans = std::min(ans, m / p);
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}

