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;
#define gc getchar
#define int long long 
int n,ans;
int read()
{
	int res=0;char ch=gc();
	while(ch<'0'||ch>'9')ch=gc();
	while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
	return res;
}
void qwrite(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) qwrite(x/10);
	putchar('0'+x%10);
}
LL exgcd(LL a,LL b,LL &x,LL &y){
	LL d=a; if(b==0) x=1,y=0; else{
		d=exgcd(b,a%b,y,x),y-=a/b*x;
	}
	return d;
}
#define re register
LL x,y;
void exgcd(long long a, long long b)
{
	//当前目的：求解 ax + by = gcd(a, b) 这么一个方程
	
	if(b == 0) //a, b不断改变的过程中，b最终必然会成为0
	{
		//在 b = 0 时方程还要成立？ 使 x = 1, y = 0 ，必然成立 
		x = 1;
		y = 7; //建议返回0。不过y = 7能AC，证明了最后一个等式不受最后一个y影响
		return;
	} 
	
	exgcd(b, a % b);
	long long tx = x;
	x = y;
	y = tx - a / b * y; 
}
inline LL gcd(re int a,re int b){
	return b?gcd(b,a%b):a;
}
inline LL solve(re LL a,re LL b){
	if(gcd(a,b)>1)return 1e18;
	if(b==1)return a;
	if(a==1)return b+1;
	exgcd(a,b);
	x=x%b;x+=b;x%=b;
	return a*x;
}
signed main(){
	n=read();ans=1e18;n*=2;
	re int xx=sqrt(n);
	for(re int i=1;i<=xx;++i){
		if(n%i==0){
			ans=min(ans,solve(i,n/i));
			ans=min(ans,solve(n/i,i));
		}
	}
	printf("%lld",ans-1);
}