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>

typedef long long LL;

using namespace std;

array<LL, 2> find_alphas(LL a, LL b) {
	if (b == 0)
		return {1, 0};
	auto result = find_alphas(b, a % b);
	LL k = a / b;
	return {result[1], (result[0] - result[1] * k)};
}

LL gcd(LL a, LL b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

LL solve_test(LL n) {
	n *= 2;

	LL min_k = n - 1;
	for (LL i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			LL n1 = i;
			LL n2 = n / i;
			if (gcd(n1, n2) == 1) {
				auto alphas = find_alphas(n1, n2);
				LL k;
				if (alphas[0] < 0)
					k = -alphas[0] * n1;
				else
					k = -alphas[1] * n2;
				min_k = min(min_k, k);
			}
		}
	}

	return min_k;
}

int random_test() {
	return rand();
}

bool check_solution(LL n, LL k) {
	if (k * (k + 1) / 2 % n == 0)
		return true;
	return false;
}

int main() {
	LL n;
	cin >> n;
	cout << solve_test(n) << '\n';

	return 0;
}
