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<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef __int128 i128;
ll n;
int ds;
ll d[25],np[25];
ll ans;
void div(ll tn){
	for(ll i=2;i*i<=tn;i++){
		if(tn%i) continue;
		d[++ds]=1; np[ds]=i;
		while(tn%i==0) tn/=i,d[ds]*=i;
	}
	if(tn>1) d[++ds]=tn,np[ds]=tn;
}
ll qmult(i128 ta,i128 tb,ll mod){
	return ta*tb%mod; 
}
ll ksm(ll ta,ll tp,ll mod){
	ll s=1;
	for(;tp;ta=qmult(ta,ta,mod),tp>>=1) if(tp&1) s=qmult(ta,s,mod);
	return s;
}
ll calc(ll s1){
	ll s2=2*n/s1,phi,k;
	phi=s2;
//	printf("%lld %lld\n",s1,s2);
	if(s2==1) return s1;
	for(int i=1;i<=ds;i++)
		if(s2%np[i]==0) phi=phi/np[i]*(np[i]-1);
	k=ksm(s1,phi-1,s2);
	k=s2-k;
	return k*s1;
}
void dfs(int i,ll s){
	if(i==ds+1){
		ans=min(ans,calc(s));
		return;
	}
	dfs(i+1,s*d[i]);
	dfs(i+1,s);
}
int main(){
	scanf("%lld",&n);
	div(n*2);
	ans=2*n;
	dfs(1,1);
	printf("%lld\n",ans);
	return 0;
}
