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 ll long long
#define vl __int128
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

ll n, an;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void gcd(ll a, ll b, ll &c, ll &d, ll &e) {
	if (b) {
		gcd(b, a%b, d, c, e);
		d -= a / b*c;
	}
	else c = 1, d = 0, e = a;
}

ll pw(ll x, ll p, ll md){
	ll an = 1;
	while(p){
		if (p & 1)an = (vl)an * x % md;
		x = (vl)x * x % md;
		p >>= 1;
	}
	return an;
}

bool ok(ll x) { return x && !((vl)x * (x + 1) / 2 % n); }

void go(ll x){
	ll y = n / gcd(x, n);
	ll z, t, g;
	gcd(y, x, z, t, g);
	if (g > 1)return;
	if (z < 0)z += x;
	if (ok(y * z - 1))an = min(an, y * z - 1);
	else if (y * z > 1)go(x * 2);
}

int main(){
	scanf("%lld", &n);
	if (n == 1){
		printf("1\n");
		return 0;
	}
	if (n & 1)an = n - 1;
	else an = 2 * n - 1;
	for (int i = 2; (ll)i * i <= n; ++i)if (n % i == 0){
		go(i);
		if ((ll)i * i != n)go(n / i);
	}
	printf("%lld\n", an);
}