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 pair < int , int > pii;
#define mpr make_pair
#define FS first
#define SC second
#define PB push_back
template < typename T > void UMAX(T &a,T b){a=(a>b?a:b);}
template < typename T > void UMIN(T &a,T b){a=(a<b?a:b);}
LL readint(){
	char c=getchar();
	LL ret=0ll;
	bool neg=0;
	while(!(c>='0' && c<='9')){
		if(c=='-') neg=1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		ret=ret*10ll+(LL)(c-'0');
		c=getchar();
	}
	return neg?-ret:ret;
}
void putint(LL v){
	if(v<0){
		putchar('-');
		v=-v;
	}
	if(!v){
		putchar('0');
		return;
	}
	if(v>=10ll) putint(v/10ll);
	putchar('0'+(v%10ll));
}
LL N;
LL gcd(LL A,LL B){
	if(!B) return A;
	return gcd(B,A%B);
}
void exgcd(LL A,LL B,LL &X,LL &Y){// AX-BY=1
	if(!B){
		X=1;Y=0;
		return;
	}
	exgcd(B,A%B,X,Y);
	LL nX=-Y,nY=-X-(A/B)*Y;
	if(nX<0){
		LL mtp=(-nX+B-1)/B;
		nX+=B*mtp;
		nY+=A*mtp;
	}
	if(nY<0){
		LL mtp=(-nY+A-1)/A;
		nX+=B*mtp;
		nY+=A*mtp;
	}
	LL mtp=min(nX/B,nY/A);
	nX-=B*mtp;
	nY-=A*mtp;
	X=nX;Y=nY;
}
void exgcd2(LL A,LL B,LL &X,LL &Y){
	if(A==1){
		X=B+1;
		Y=1;
		return;
	}
	if(B==1){
		X=1;
		Y=A-1;
		return;
	}
	exgcd(A,B,X,Y);
}
int main(){
	int i,j,k;
	N=readint()*2;
	LL res=(LL)8e18;
	for(i=1;(LL)i*i<=N;++i){
		if(N%i) continue;
		if(gcd(i,N/i)>1) continue;
		LL x,y;
		exgcd2(i,N/i,x,y);
		UMIN(res,x*i-1);
		exgcd2(N/i,i,x,y);
		UMIN(res,y*i);
	}
	printf("%lld\n",res);
	return 0;
}
