Example

Input

3


Output

1
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

using ll = long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll mod_pow(ll a, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if (n % 2 == 1) (res *= a) %= m;
        (a *= a) %= m;
        n /= 2;
    }
    return res;
}

map<int, int> factorize(int x) {
    map<int, int> res;
    for (int d = 2; d * d <= x; ++d) {
        int count = 0;
        while (x % d == 0) {
            ++count;
            x /= d;
        }
        if (count > 0) res[d] = count;
    }
    if (x > 1) res[x] = 1;
    return res;
}

int euler_totient(int x) {
    int res = x;
    for (int y = 2; y * y <= x; ++y) {
        if (x % y == 0) {
            res -= res / y;
            while (x % y == 0) x /= y;
        }
    }
    if (x > 1) res -= res / x;
    return res;
}

int N;

int main(void) {
    cin >> N;

    auto n_factors = factorize(N);
    ll L = 1;
    for (auto& itr : n_factors) {
        if (itr.second > 1) {
            cout << -1 << endl;
            exit(0);
        }
        L = lcm(L, itr.first - 1);
    }

    if (gcd(N, L) > 1) {
        cout << -1 << endl;
        exit(0);
    }

    const int el = euler_totient(L);
    int ans = el;
    for (int x = 1; x * x <= el; ++x) {
        if (el % x == 0) {
            if (mod_pow(N, x, L) == 1)
                ans = min(ans, x);
            if (mod_pow(N, el / x, L) == 1)
                ans = min(ans, el / x);
        }
    }

    cout << ans << endl;


    return 0;
}

