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;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

ll n, ans = -1;

ll exgcd(ll a, ll b, ll &x, ll &y){
	if(!b){
		x = 1; y = 0;
		return a;
	}
	ll g = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return g;
}

inline void solve(ll a, ll b){ // min x satisfying ax - by = 1, x, y \in \Z, a < b
	ll x, y, g = exgcd(a, b, x, y);
//	printf("a = %lld b = %lld x = %lld y = %lld\n", a, b, x, y);
	if(g != 1)
		return;
	// now we get ax + by = 1
	y = -y;
	b = -b;
	// now we get ax - by = 1
	if(y <= 0){
		ll k = (abs(y) + a / g) / (a / g);
		y += k * (a / g);
		x -= k * (b / g);
	}
	if(x <= 0)
		return;
	ll k = (x - 1) / (b / g);
	x += k * (b / g);
	y -= k * (a / g);
	if(log10(a) + log10(x) <= 18 && (ans == -1 || ans > a * x - 1))
		ans = a * x - 1;
	return;
}

int main(){
	scanf("%lld", &n);
	n <<= 1;
	for(ll a = 1; 1ll * a * a <= n; ++a) if(!(n % a)){
		ll b = n / a;
		solve(a, b);
		if(a != b)
			solve(b, a);
	}
	printf("%lld\n", ans);
	return 0;
}
