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;
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;
}
