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;
long long extgcd(long long a, long long b, long long &x, long long &y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	long long g = extgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return g;
}
inline long long calcinv(long long a, long long m) {
	long long x, y;
	extgcd(a, m, x, y);
	return (x % m + m) % m;
}
vector<pair<long long, long long> > FF(long long n) {
	vector<pair<long long, long long> > vec;
	for (long long i = 2; i * i <= n; i++) if (n % i == 0) {
		int cc = 0;
		long long pp = 1;
		while (n % i == 0) {
			cc++;
			n /= i;
			pp *= (long long)i;
		}
		vec.push_back(make_pair(i, pp));
	}
	if (n > 1) vec.push_back(make_pair(n, n));
	return vec;
}
long long m1[100], m2[100];
int main() {
	long long n;
	cin >> n;
	if (n % 2 == 0) {
		n *= 2;
	}
	vector<pair<long long, long long> > vec = FF(n);
	for (int i = 0; i < (int)vec.size(); i++) {
		m1[i] = n / vec[i].second;
		m2[i] = calcinv(m1[i] % vec[i].second, vec[i].second);
	}
	long long ans = 0;
	for (int mask = 1; mask < (1 << vec.size()); mask++) {
		long long cur = 0;
		for (int i = 0; i < (int)vec.size(); i++) if (mask >> i & 1) {
			cur += m1[i] * m2[i];
		}
		cur %= n;
		ans = max(ans, cur);
	}
	cout << n - ans << endl;
	return 0;
}