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 n,n1=1,n2=1,ans;
bool vis[31622996];
long long prime[31622996],p[29];
int cnt,cnt2,dep;


void dfs() {
	if(dep==cnt2) {
		long long x=n1,y=n2,ax=1,bx=0,ay=0,by=1;
		if(x>y) swap(x,y),swap(ax,ay),swap(bx,by);
		//x=a*n1+b*n2 y=a*n2+b*n2
		//a*n1+b*n2=1
		while(x!=1) {
			ay-=(y/x)*ax,by-=(y/x)*bx;
			y%=x;
			swap(x,y),swap(ax,ay),swap(bx,by);
		}
//		cout<<n1<<' '<<n2<<' '<<ax<<' '<<bx<<'\n';
		if(ax==0||bx==0) return;
		ans=min(((-bx)%n1+n1)%n1*n2,ans);
		ans=min(((-ax)%n2+n2)%n2*n1,ans);
		return;
	}
	n1*=p[dep++];
	dfs();
	n1/=p[dep-1],n2*=p[dep-1];
	dfs();
	n2/=p[--dep];
}

int main(void) {
	for(register int i=2; i<31622776; ++i) 
		if(!vis[i]) {
			prime[cnt++]=i;
			for(register int j=i; j<31622776; j+=i) 
				vis[j]=1;
		}
	cin>>n;
	if(n==1) {
		cout<<1;
		return 0;
	}
	n*=2,ans=n;
	for(int i=0; i<cnt; ++i)
		if(n%prime[i]==0) {
			p[cnt2]=1;
			while(n%prime[i]==0)
				n/=prime[i],p[cnt2]*=prime[i];
			++cnt2;
		}
	if(n!=0) p[cnt2++]=n;
	dfs();
	cout<<ans;
}