Given is an integer N. Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N. It can be proved that such a positive integer k always exists.

Constraints

* 1 \leq N \leq 10^{15}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N


Output

Print the answer in a line.

Examples

Input

11


Output

10


Input

20200920


Output

1100144
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

vector <ll> p;

void factor(ll x) {
	for (int i = 2; 1LL * i * i <= x; ++ i) {
		if (x % i == 0) {
			ll c = 1;
			while (x % i == 0) {
				c *= i;
				x /= i;
			}
			p.pb(c);
		}
	}
	if (x > 1) {
		p.pb(x);
	}
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1; y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main() {
	ll n;
	scanf("%lld", &n);
	n *= 2;
	factor(n);
	ll ans = n;
	rep(S, 1 << p.size()) {
		ll a = 1, b = 1;
		rep(i, p.size()) (S >> i & 1 ? a : b) *= p[i];
		ll x, y;
		exgcd(a, b, x, y);
		a *= -1;
		a *= x; b *= y;
		ll delt = max(0LL, -min(a, b));
		delt = (delt + n - 1) / n;
		a += delt * n;
		b += delt * n;
		if (a > 0) ans = min(ans, a);
	}
	printf("%lld\n", ans);
	return 0;
}
