Example

Input

3


Output

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

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int calc_order(long long N, long long L) {
    auto pf = prime_factorize(L);
    long long euler = L;
    for (auto pa : pf) {
        int p = pa.first;
        euler /= p, euler *= p-1;
    }
    
    long long res = euler;
    auto pfeuler = prime_factorize(euler);
    for (auto pa : pfeuler) {
        int p = pa.first;
        while (res % p == 0 && modpow(N, res/p, L) == 1) res /= p;
    }
    return res;
}

long long solve(long long N) {
    auto pf = prime_factorize(N);
    
    bool ok = true;
    long long L = 1;
    for (auto p : pf) {
        if (p.second > 1) ok = false;
        long long g = GCD(L, p.first - 1);
        L = L / g * (p.first - 1);
    }
    if (!ok) return -1;
    if (GCD(N, L) > 1) return -1;
    if (L == 1) return 1; // 例外処理

    // mod L での N の位数を求める
    return calc_order(N, L);
}

int main() {
    long long N; cin >> N;
    cout << solve(N) << endl;
}

