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>
typedef long long ll;
__int128 x, y;
void exgcd(ll a, ll b){
	if(b == 0){
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b);
	ll tmp = x; x = y, y = tmp - (__int128)(a / b) * y;
}
ll n;
int bit;
std::vector<std::pair<ll, int> > d;
ll val[100];
ll ans = 1e18;
int main(){
	std::scanf("%lld", &n); n *= 2;
	if(n == 2){
		std::puts("1");
		return 0;
	}
	ll r(n);
	for(int i = 2; (ll)i * i <= r; ++i)
		if(r % i == 0){
			int cnt = 0;
			while(r % i == 0) r /= i, ++cnt;
			d.push_back({i, cnt});
		}
	if(r != 1) d.push_back({r, 1});
	int bit = d.size();
	for(int i = 0; i < bit; ++i){
		val[i] = 1;
		for(int j = 0; j < d[i].second; ++j) val[i] *= d[i].first;
	}
	for(int S = 1; S < (1 << bit); ++S){
		ll a = 1, b = 1;
		for(int j = 0; j < bit; ++j)
			if(S & (1 << j)) a *= val[j];
			else b *= val[j];
		exgcd(a, b);
		x = (x % b + b) % b, y = (x % a + a) % a;
		if(x * a == 1) x += b;
	//	std::printf("%lld %lld %lld %lld\n", a, b, (ll)x, (ll)y);
		x *= a; if(x && x - 1 < ans) ans = x - 1;
		std::swap(a, b);
		exgcd(a, b);
		x = (x % b + b) % b, y = (x % a + a) % a;
		if(x * a == 1) x += b;
	//	std::printf("%lld %lld %lld %lld\n", a, b, (ll)x, (ll)y);
		x *= a; if(x && x - 1 < ans) ans = x - 1;
	}
	std::printf("%lld\n", ans);
}