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 pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

vector <ll> spis;
ll X, Y;

ll nod(ll A, ll B)
{
 	if (A == 0) {X = 0, Y = 1; return 1;}
 	ll d = nod(B % A, A);
 	ll newX = -Y - (B / A) * X;
 	ll newY = -X;
 	X = newX, Y = newY;
 	return d;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	ll A;
 	cin >> A;
 	A *= 2;
 	ll answer = A;

 	ll uk = 2;
 	while (uk * uk <= A)
 	{
 	 	ll step = 1;
 	 	while (A % uk == 0) A /= uk, step *= uk;
 	 	if (step != 1) spis.pb(step);
 	 	uk++;
 	}
 	if (A != 1) spis.pb(A);

 	int sz = (int) spis.size();
 	for (int mask = 0; mask < (1 << sz); mask++)
 	{
 	 	ll fir = 1, sec = 1;
 	 	for (int i = 0; i < sz; i++)
 	 		if (((mask >> i) & 1) != 0) fir *= spis[i];
 	 		else sec *= spis[i];
 	 	ll d = nod(fir, sec);

 	 	if (X <= 0) X += ((-X) / sec + 1) * sec;
 	 	X %= sec;
 	 	if (X == 0) X = sec;
 	 	answer = min(answer, X * fir);
 	}
 	cout << answer << '\n';
 	return 0;
}