#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

typedef __int128 lll;
ll n;

inline void exgcd(lll a, lll b, lll &x, lll &y) {b ? (exgcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0);}
inline ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

int main() {
	cin >> n; n *= 2;
	ll ans = n;
	for(ll i = 1; i * i <= n; i++) {
		if(n % i) continue;
		ll now = i;
		lll x, y;
		if(gcd(now, n / now) == 1) {
			exgcd(n / now, now, x, y);
			y = -y; ((y %= n / now) += n / now) %= n / now;
			if(y) ans = min(ans, ll(y * now));
		}
		now = n / i;
		if(gcd(now, n / now) == 1) {
			exgcd(n / now, now, x, y);
			y = -y; ((y %= n / now) += n / now) %= n / now;
			if(y) ans = min(ans, ll(y * now));
		}
	}
	cout << ans << endl;
	return 0;
}
