Example

Input

3


Output

1
#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

long long gcd(long long a, long long b) {
    while (b > 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

long long powmod(long long a, long long b, long long mod) {
    if (b == 0) return 1;
    long long p = powmod(a, b / 2, mod);
    p = p * p % mod;
    if (b & 1) p = p * a % mod;
    return p;
}

int main() {
    int n;
    cin >> n;
    int m = n;
    vector<int> v;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            if (n % (i * i) == 0) {
                cout << "-1\n";
                return 0;
            }
            v.push_back(i);
            n /= i;
        }
    }
    if (n > 1) v.push_back(n);
    long long l = 1;
    for (auto& a : v) l = lcm(l, a - 1);
    if (gcd(m, l) > 1) {
        cout << "-1\n";
        return 0;
    }
    long long p = l;
    long long cnt = l;
    for (int i = 2; i * i <= l; ++i) {
        if (l % i == 0) {
            cnt = cnt / i * (i - 1);
            while (l % i == 0)
                l /= i;
        }
    }
    if (l > 1) cnt = cnt / l * (l - 1);

    long long ans = cnt;
    for (long long i = 1; i * i <= cnt; ++i) {
        if (cnt % i == 0) {
            if (powmod(m, i, p) == 1)
                ans = min(ans, i);
            if (powmod(m, cnt / i, p) == 1)
                ans = min(ans, cnt / i);
        }
    }
    cout << ans << "\n";
    return 0;
}

