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 <cstdio>
#include <cstdlib>
template<typename Elem>
Elem min(Elem a,Elem b){
	return a<b?a:b;
}
template<typename Elem>
void read(Elem &a){
	a=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a=(a<<1)+(a<<3)+(c^48);
		c=getchar();
	}
}
//const long long One=1;
const __int128 One=1;
template<typename Elem>
Elem quick_power(Elem a,Elem b,Elem Mod){
	Elem ans=1;
	while(b){
		if(b&1){
			ans=One*ans*a%Mod;
		}
		b>>=1;
		a=One*a*a%Mod;
	}
	return ans;
}
const int Maxn=100;
typedef long long ll;
const ll Inf=0x3f3f3f3f3f3f3f3fll;
ll s;
ll p[Maxn+5],q[Maxn+5];
int len;
void work(ll n){
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			p[++len]=1;
			q[len]=i;
			while(n%i==0){
				n/=i;
				p[len]*=i;
			}
		}
	}
	if(n>1){
		p[++len]=n;
		q[len]=n;
	}
}
int main(){
	scanf("%lld",&s);
	ll ans=Inf;
	if(s&1){
		ans=s;
	}
	else{
		ans=s-1;
	}
	work(s<<1);
	for(int i=0;i<(1<<len);i++){
		ll p_1=1,p_2=1,phi_p=1;
		for(int j=1;j<=len;j++){
			if((i>>(j-1))&1){
				p_1*=p[j];
			}
			else{
				p_2*=p[j];
				phi_p*=p[j]/q[j]*(q[j]-1);
			}
		}
		if(p_2==1){
			continue;
		}
		ll k=One*(p_2-1)*quick_power(p_1,phi_p-1,p_2)%p_2;
		ans=min(ans,k*p_1);
	}
	printf("%lld\n",ans);
	return 0;
}
