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 pair<ll, ll> pll;
#define mp(a, b) make_pair(a, b)
ll ans;
ll exgcd(ll a, ll b, ll & x, ll & y)
{
	if(!b)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, x, y);
	ll t = x;
	x = y;
	y = t - (a / b) * y;
	return d;
}
pll get(ll a, ll b, ll c)
{
	ll x, y;
	ll d = exgcd(a, b, x, y);
	if(c % d != 0) return mp(-1, -1);
	x *= c / d;
	y *= c / d;
	b = abs(b / d);
	a = abs(a / d);
	x %= b;
	y %= a;
	if(x <= 0) x += b;
	if(y <= 0) y += a;
	return mp(x, y);
}
void calc(ll a, ll b)
{
	pll ret = get(b, -a, 1);
	if(ret.first == -1) return;
	//cout << a << ' ' << ret.second << ' ' << b << ' ' << ret.first << endl;
	ans = min(max(ret.first * b - 1, ret.second * a), ans);
}
int main()
{
	ll N;
	scanf("%lld", &N);
	ans = 2 * N;
	for(ll i = 1; i * i <= N; ++i)
		if(N % i == 0)
		{
			calc(2 * i, N / i);
			calc(i, 2 * N / i);
			calc(2 * N / i, i);
			calc(N / i, 2 * i);
		}
	printf("%lld\n", ans);
	return 0;
}