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;
typedef long long LL;
typedef double db;
#define pb(x) push_back(x)
#define mkp(x,y) make_pair(x,y)
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
#define int long long
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return x*f;
}
int n,tot,ans,a[100];
void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
int solve(int a,int b){
	int x,y;
	exgcd(a,b,x,y);
	x=(x%b+b)%b;
	if(!x)x=b;
	y=(1-a*x)/b;
	y=-y;
	if(y<=0) return n;
//	cout << a <<" "<< b <<" "<< x <<" "<< y <<" "<< a * x<< endl;
	return a*x;
}
bool isp(int x){
	for(int i=2;i*i<=x;++i)if(x%i==0)return 0;
	return 1;
}
signed main(){
	cin>>n, ans = 2 * n;
	if(n==1) puts("1"),exit(0);
	n=n*2;
	int tmp=n;
	for(int i=2;i*i<=tmp;++i){
		if(tmp%i==0){
			++tot,a[tot]=1;
			while(tmp%i==0)tmp/=i,a[tot]*=i;
		}
	}
	if(tmp)a[++tot]=tmp;
	for(int msk=0;msk<(1<<tot)-1;++msk){
		int x=1,y=1;
		for(int j=0;j<tot;++j)
			if(msk>>j&1)x*=a[j+1];
			else y*=a[j+1];
		ans=min(ans,min(solve(x,y),solve(y,x)));
	}
	cout<<ans-1<<endl;
}