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 ext_gcd(long long a, long long b, long long &p, long long &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    long long d = ext_gcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}
long long mod_inv(long long a, long long m) {
	long long x, y;
	long long d = ext_gcd(a, m, x, y);
	x %= m;
	if (x < 0) x += m;
	return x;
}
long long garner(vector<long long> r, vector<long long> m){
	int n = r.size();
	long long m_prod = 1;
	long long x = r[0] % m[0];
	for (long long i = 1; i < n; i++) {
		m_prod *= m[i - 1];
		long long t = (((r[i] - x + m[i]) % m[i]) * mod_inv(m_prod, m[i])) % m[i];
		if (t < 0) t += m[i];
		x += t * m_prod;
	}
	return x;
}
int main(){
	long long N; cin >> N; 
	if(N == 1){
		cout << 1 << "\n"; return 0; 
	}
	long long now = N * 2; 
	vector<long long> M; 
	for(long long i = 2; i * i <= N * 2; i++){
		if(now % i != 0) continue;
		long long mul = 1LL;  
		while(now % i == 0){
			mul *= i; now /= i; 
		}
		M.emplace_back(mul); 
	}
	if(now > 1){
		M.push_back(now); 
	}
  reverse(M.begin(), M.end()); 
	int D = M.size(); 
	long long ans = N * 2; 
	for(int i = 0; i < (1 << D); i++){
		vector<long long> R; 
		for(int j = 0; j < D; j++){
			if((i >> j) & 1) R.emplace_back(M.at(j) - 1); 
			else R.emplace_back(0); 
		}
		long long tmp = garner(R, M); 
		if(tmp == 0) tmp += N * 2; 
		ans = min(ans, tmp); //cout << tmp << endl; 
	}
	cout << ans << endl; 
}