#include<cstdio>
#include<random>
#include<algorithm>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define ll long long
#define sub(x,y) (x < y ? x + n - y : x + y)
using namespace std;
ll n,f[70],g[70];
mt19937_64 gen(114514);
inline ll mul(ll x,ll y,ll n)
{
	return (__int128)(x) * y % n;
//	ll z = x * y - (ll)(1.0L * x * y / n) * n;
//	if(z > n) z -= n;
//	return z < 0 ? z + n : z;
}
ll ksm(ll x,ll y,ll n)
{
	ll res = 1;
	for(;y;y >>= 1,x = mul(x,x,n)) if(y & 1) res = mul(res,x,n);
	return res;
}
bool wit(ll a,ll n)
{
	ll u = n - 1,t = 0;
	while(u + 1 & 1) u >>= 1,++t;
	a = ksm(a,u,n);
	fo(i,1,t)
	{
		ll A = mul(a,a,n);
		if(A == 1) return a == 1 || a == n - 1;
		a = A;
	}
	return a == 1;
}
bool mr(ll n)
{
	if(n < 2) return 0;
	if(n == 2) return 1;
	fo(i,1,20)
	{
		ll a = gen() % (n - 2) + 2;
		if(wit(a,n) == 0) return 0;
	}
	return 1;
}
inline ll F(ll x,ll c,ll n)
{
	ll res = mul(x,x,n) + c;
	return res < n ? res : res - n;
}
void factor(ll n)
{
	if(n == 1) return;
	if(n + 1 & 1) {f[++f[0]] = 2;return factor(n >> 1);}
	if(mr(n)) {f[++f[0]] = n;return;}
	while(1)
	{
		ll c = gen() % (n - 1) + 1,x = gen() % (n - 1) + 1,y = x,M = 1;
		while(1)
		{
			fo(i,0,127)
			{
				x = F(x,c,n),y = F(F(y,c,n),c,n);
				ll nM = mul(sub(x,y),M,n);
				if(nM == 0) break;
				M = nM;
			}
			ll g = __gcd(M,n);
			if(g >= 2 && g <= n - 1) {factor(g),factor(n / g);return;}
			if(x == y) break;
		}
	}
}
int main()
{
	scanf("%lld",&n);
	if(n == 2) return puts("1"),0;
	else if(n == 4) return puts("3"),0;
	else if(n == 1 || n % 4 == 0) return puts("-1"),0;
	factor(n),sort(f + 1,f + f[0] + 1);
	ll ph = n;
	if(f[1] == 2)
	{
		fo(i,3,f[0]) if(f[i] != f[i - 1]) return puts("-1"),0;
		ph >>= 1;
		if(f[0] > 2) g[++g[0]] = f[2];
		f[0] = 0,ph = ph / f[2] * (f[2] - 1);
		factor(f[2] - 1);
	}
	else
	{
		fo(i,2,f[0]) if(f[i] != f[i - 1]) return puts("-1"),0;
		if(f[0] > 1) g[++g[0]] = f[1];
		f[0] = 0,ph = ph / f[1] * (f[1] - 1);
		factor(f[1] - 1);
	}
	fo(i,1,g[0]) f[++f[0]] = g[i];
	g[0] = 0,sort(f + 1,f + f[0] + 1),g[++g[0]] = f[1];
	fo(i,2,f[0]) if(f[i] != f[i - 1]) g[++g[0]] = f[i];
	fo(i,2,10000)
	{
		if(__gcd((ll)(i),n) > 1) continue;
		bool bz = 1;
		fo(j,1,g[0]) if(ksm(i,ph / g[j],n) == 1) {bz = 0;break;}
		if(bz) return printf("%d\n",i),0;
	}
}
/*#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];

void solve() {
    int n, m; cin >> n >> m;
    int curv = n;
    map<pair<int, int>, int> pos;
    int p0, p1;
    for (int i = 0; i < m; i++) {
        int b, g; cin >> b >> g;
        if (i == 0) p0 = b;
        if (i == 1) p1 = b;
        if (pos.find({b % g, g}) != pos.end()) {
            int step = (b - b % g) / g;
            g_lol[b].pb(pos[{b % g, g}] + step);
            continue;
        }
        pos[{b % g, g}] = curv;
        int step = (b - b % g) / g;
        g_lol[b].pb(pos[{b % g, g}] + step);
        for (int j = b % g; j < n; j += g) {
            val[curv] = j;
            stepp[curv] = g;
            curv++;
        }
    }
    for (int i = 0; i < curv; i++) dist[i] = 1e9;
    dist[p0] = 0;

    deque<int> q;
    q.push_back(p0);
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        if (v < n) {
            for (int el : g_lol[v]) {
                if (dist[el] > dist[v]) {
                    dist[el] = dist[v];
                    q.push_front(el);
                }

}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}*/