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>
using namespace std;

pll egcd(ll m, ll n) {
	if (n==0) return {1, 0};
	pll tmp = egcd(n, m%n);
	ll x = tmp.first, y = tmp.second;
	return {y, x - (m/n)*y};
}

ll my_ceil(ll x, ll y) {
	return x/y + (x%y>0);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	#ifdef LOCAL
//		freopen("in1.txt", "r", stdin);
//		freopen("in1.txt", "w", stdout);
	#endif
	ll n;
	cin >> n;
	if (n==1) {
		cout << 1 << '\n';
		return 0;
	}
	else if (n==2) {
		cout << 3 << '\n';
		return 0;
	}
	ll tmp = n;
	vector<pll> prm;
	int two = 1;
	while (tmp%2 == 0) {
		tmp /= 2;
		two++;
	}
	prm.push_back({2, two});
	for (ll i=2; i*i<=tmp; i++) {
		if (tmp%i == 0) {
			int cnt = 0;
			while (tmp%i==0) {
				tmp /= i;
				cnt++;
			}
			prm.push_back({i, cnt});
		}
	}
	if (tmp>1) prm.push_back({tmp, 1});
	
	int m = prm.size();
	vector<ll> num(m);
	for (int i=0; i<m; i++) {
		ll cur = 1;
		while (prm[i].second--) cur *= prm[i].first;
		num[i] = cur;
	}
	
	ll ans = n-1;
	int sz = (1<<m);
	for (int i=0; i<sz; i++) {
		ll p = 1, q = 1;
		for (int b=0, bit=1; b<m; b++, bit<<=1) {
			if (i&bit) p *= num[b];
			else q *= num[b];
		}
		if (p==1 || q==1) continue;
		pll sol = egcd(p, -q);
//		cout << p << ' ' << q << ' ' << sol.first << ' ' << sol.second << '\n';
		ll x = sol.first;
		x %= q;
		x = (x+q) % q;
		ans = min(ans, p*x);
	}
	cout << ans << '\n';
}