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;
//https://qiita.com/drken/items/ae02240cd1f8edfc86fd
// 負の数にも対応した mod
// 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
// しかし単に -17 % 5 では -2 になってしまう
inline long long mod(long long a, long long m) {
	return (a % m + m) % m;
}

// 拡張 Euclid の互除法
// ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
long long extGcd(long long a, long long b, long long &p, long long &q) {
	if (b == 0) { p = 1; q = 0; return a; }
	long long d = extGcd(b, a%b, q, p);
	q -= a / b * p;
	return d;
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(long long b1, long long m1, long long b2, long long m2) {
	long long p, q;
	long long d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
	if ((b2 - b1) % d != 0) return make_pair(0, -1);
	long long m = m1 * (m2 / d); // lcm of (m1, m2)
	long long tmp = (b2 - b1) / d * p % (m2 / d);
	long long r = mod(b1 + m1 * tmp, m);
	return make_pair(r, m);
}

//約数列挙
vector<long long> calc(long long N) {
	vector<long long> x;
	for (long long i = 1; i <= sqrt(N); i++) {
		if (0 == N % i) {
			x.push_back(i);
			if (N != i * i) {
				x.push_back(N / i);
			}
		}
	}
	sort(x.begin(), x.end());
	return x;
}

int main() {
	long long N;
	cin >> N;
	N *= 2;
	vector<long long>v = calc(N);
	long long ans = 1e18;
	for (int i = 0; i < v.size(); ++i) {
		pair<long long, long long> res = ChineseRem(0, v[i], -1, N / v[i]);
		if (-1 != res.second) {
			if (0 != res.first) {
				ans = min(ans, res.first);
			}
			else {
				ans = min(ans, res.second);
			}
		}
	}
	cout << ans << endl;
	return 0;
}