Example

Input

3


Output

1
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
typedef pair<int, int> P;

int n;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

int power(int a, int n) {
	if (n == 0) return 1;
	if (n & 1) return a * power(a, n - 1);
	return power(a * a, n / 2);
}

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n & 1) return (a * powmod(a, n - 1, mod)) % mod;
	return powmod((a * a) % mod, n / 2, mod);
}

vector<P> factorize(int n) {
	int t = n;
	vector<P> ret;
	
	for (int i = 2; i * i <= t; i++) {
		int cnt = 0;
		while (t % i == 0) {
			t /= i;
			cnt++;
		}
		if (cnt > 0) {
			ret.push_back(P(i, cnt));
		}
	}
	if (t > 1) {
		ret.push_back(P(t, 1));
	}
	return ret;
}

signed main() {
	cin >> n;
	if (n == 2) { cout << 1 << endl; return 0; }
	else if (n % 2 == 0) { cout << -1 << endl; return 0; }
	for (int m = 2; m * m <= n; m++) { if (n % (m * m) == 0) { cout << -1 << endl; return 0; } }
	
	vector<P> p = factorize(n);
	int L = 1;
	for (int i = 0; i < p.size(); i++) L = lcm(L, p[i].first - 1);
	vector<P> q = factorize(L);
	
	int ans = 1;
	for (int i = 0; i < q.size(); i++) {
		int a = power(q[i].first, q[i].second);
		if (gcd(n, a) != 1) { cout << -1 << endl; return 0; }
		int eq = a - power(q[i].first, q[i].second - 1);
		//eq????´???°???????£?
		int minK = eq;
		for (int k = 1; k * k <= eq; k++) {
			if (eq % k != 0) continue;
			if (powmod((n % a), k, a) == 1) minK = min(minK, k);
			if (powmod((n % a), eq / k, a) == 1) minK = min(minK, eq / k);
		}
		//lcm?????????
		ans = lcm(ans, minK);
	}
	cout << ans << endl;
	return 0;
}