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 <stdio.h>
#include <algorithm>
using namespace std;

typedef long long int ll;
constexpr ll kInf = ll(1E18 + 10);

ll extgcd(ll a, ll b, ll &x, ll &y) { // a * x - b * y = gcd
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	else {
		ll tx, ty;
		ll gcd = extgcd(b, a % b, tx, ty);
		// b * tx - (a % b) * ty = gcd
		// b * tx - (a - a / b * b) * ty = gcd
		// b * tx - a * ty + a / b * b * ty = gcd
		// a * -ty + b * (tx + a / b * ty) = gcd
		x = -ty;
		y = -(tx + a / b * ty);
		
		y %= a;
		x = (gcd + b * y) / a;
		if (y <= 0) {
			x += b;
			y += a;
		}
		return gcd;
	}
}

ll check(ll p, ll q) {
	//p * x - q * y = 1
	ll x, y;
	if (extgcd(p, q, x, y) > 1) return kInf;
	else {
		return q * y;
	}
}

int main() {
	ll n, ans;
	scanf("%lld", &n);
	n <<= 1;
	ans = n;
	for (ll i = 1; i * i <= n; i++) if (n % i == 0) 
		ans = min(ans, min(check(i, n / i), check(n / i, i)));
	printf("%lld\n", ans);
}
