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>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
//const int MAXN = 200005;
//const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 1e9 + 7;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

pair<LL, LL> ext_gcd( LL a, LL b) {
	if (b == 0) return make_pair(1, 0);
    if (a % b == 0) return make_pair(0, 1);
    pair<LL, LL> t = ext_gcd(b, a % b);
    return make_pair( t.second, t.first - a / b * t.second);
}

void solve() {
	LL n;
	cin >> n;
	
	LL tmp = 2 * n;
	vector<LL> fac;
	for (LL i = 2; i * i <= tmp; i++) {
		if (tmp % i == 0) {
			LL tot = 1;
			while (tmp % i == 0) {
				tmp /= i;
				tot *= i;
			}
			fac.push_back(tot);
		}
	}
	if (tmp != 1) {
		fac.push_back(tmp);
	}
//	cout << "Tot " << fac.size() << '\n';
	
	LL ans = 2 * n;
	for (int i = 0; i < (1 << fac.size()); i++) {
		LL l = 1, r = 1;
		for (int j = 0; j < fac.size(); j++) {
			if (i >> j & 1) l *= fac[j];
			else r *= fac[j];
		}
		PLL res = ext_gcd(l, r);
		LL k = l * -res.fi;
		
		if (k <= 0) {
			k += l * r;
		}
//		cout << "At " << l << ' ' << r << " get " << res.fi <<  ' ' << res.se << ' ' << k << endl;
//		assert(k * (k + 1) / 2 % n == 0);
		ans = min(ans, k);
	}
	
	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int tc = 1;
//	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}

	return 0;
} 