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;

int sol(int x){
	for(int i=1;i<=x;i++){
		int v=i*(i+1);
		if(v%x==0) return i;
	}
	return -1;
}
vector<pair<long long,int>> prime_divs(long long x){
	vector<pair<long long,int>> res;
	for(long long i=2;i*i<=x;i++){
		if(x%i!=0) continue;
		
		int cnt=0;
		while(x%i==0){
			x/=i;
			cnt++;
		}
		res.push_back(make_pair(i,cnt));
	}
	if(x>1) res.push_back(make_pair(x,1));
	return res;
}
__int128 inv(__int128 a,__int128 mod){
	__int128 b=mod,p=1,q=0;
	while(b){
		__int128 c=a/b,d=a;
		a=b;
		b=d%b;
		d=p;
		p=q;
		q=d-c*q;
	}
	return (p+mod)%mod;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long x;
	cin >> x;
	x*=2;
	
	vector<pair<long long,int>> pds=prime_divs(x);
	int n=(int)pds.size();
	
	long long res=x-1;
	for(int i=0;i<(1<<n);i++){
		long long le=1,ri=1;
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				for(int k=0;k<pds[j].second;k++) le*=pds[j].first;
			}else{
				for(int k=0;k<pds[j].second;k++) ri*=pds[j].first;
			}
		}
		
		if(le==1 || ri==1) continue;
		__int128 invle=inv(le,ri);
		if((res+1)/le>=invle){
			res=min(res,(long long)(le*invle-1));
		}
	}
	cout << res << "\n";
	return 0;
}