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;

bool vis[31622777];
int prime[2000000], tot;

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

void get_prime(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prime[tot++] = i;
		for (int j = 0; j < tot && 1ll * i * prime[j] <= n; j++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}

int main () {
	get_prime(31622776);
	long long n; cin >> n; n *= 2;
	long long tmp = n;
	vector <long long> all;
	for (int i = 0; i < tot; i++) {
		long long pw = prime[i];
		while (n % pw == 0) pw *= prime[i];
		pw /= prime[i];
		if (pw != 1) all.push_back(pw), tmp /= pw;
	}
	if (tmp != 1) all.push_back(tmp);
	int m = all.size();
	__int128 ans = 900000000000000000;
	for (int mask = 0; mask < (1 << m); mask++) {
		long long x = 1, y = 1;
		__int128 k1, k2;
		for (int i = 0; i < m; i++) {
			if (mask >> i & 1) x *= all[i];
			else y *= all[i];
		}
		exgcd(x, y, k1, k2);
		assert(x * k1 + y * k2 == 1);
		k2 = -k2;
		__int128 tmp = max((max((__int128)0, 1 - k1) + y - 1) / y, (max((__int128)0, 1 - k2) + x - 1) / x);
		k1 += tmp * y, k2 += tmp * x;
		if (ans / k2 >= y) ans = min(ans, k2 * y);
		k1 = -k1, k2 = -k2;
		tmp = max((max((__int128)0, 1 - k1) + y - 1) / y, (max((__int128)0, 1 - k2) + x - 1) / x);
		k1 += tmp * y, k2 += tmp * x;
		if (ans / k1 >= x) ans = min(ans, k1 * x);
	}
	cout << (long long)ans << endl;
	return 0;
}
