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
/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); i++)
#define cont(i, n)          for(int i = 1; i <= (n); i++)
#define circ(i, a, b)       for(int i = (a); i <= (b); i++)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

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