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
/*
 * Author: Kewth

 * Date:
  echo -n '  ' && date +%Y.%m.%d # Type "!!sh" in Vim.

 * Solution:
  To be updated after "Accept".

 * Digression:

 * CopyRight:
   __  __                  __   __
  |  |/  |.-----.--.--.--.|  |_|  |--.
  |     < |  -__|  |  |  ||   _|     |
  |__|\__||_____|________||____|__|__|

 */

#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

static struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator () (a...); }
} read;

ll __tmp1, __tmp2;
ll exgcd(ll a, ll b, ll &x = __tmp1, ll &y = __tmp2) {
	if(!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll x0, y0;
	ll res = exgcd(b, a % b, x0, y0);
	x = y0;
	y = x0 - a / b * y0;
	return res;
}

ll inv(ll x, ll Mod) {
	ll res;
	if (exgcd(x, Mod, res) != 1)
		return -1;
	return ((res % Mod) + Mod) % Mod;
}

ll ans = 1000000000000000000;
void solve (ll x, ll y) {
	ll iv = inv(x, y);
	if (iv == -1) return;
	ll z = iv * x - 1;
	if (z < 1) z += x * y;
	ans = std::min(ans, z);
}

int main () {
	ll n = read;
	n <<= 1;
	for (ll x = 1; x * x <= n; x ++)
		if (n % x == 0) {
			solve(x, n / x);
			solve(n / x, x);
		}
	printf("%lld\n", ans);
}
