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<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long double DB;typedef long long LL;

LL n,ans;

inline LL Mul(LL x,LL y,LL MOD) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;}
LL exgcd(LL a,LL b,LL &x,LL &y){
	if (!b) {x=1;y=0;return a;}
	LL r=exgcd(b,a%b,y,x);y-=a/b*x;return r;
}
LL Solve(LL A,LL B,LL C){
	LL x,y,r=exgcd(A,B,x,y);if (C%r) return 1e18;
	LL T=B/r;x=Mul((C/r)%T,x%T,T);
	if ((DB)A*x>1e18) return 1e18;return A*x;
}
int main(){
	scanf("%lld",&n);n<<=1;ans=n-1;
	for (int S=sqrt(n),i=2;i<=S;i++)
		if (!(n%i)) ans=min(ans,Solve(n/i,i,i-1)),ans=min(ans,Solve(i,n/i,n/i-1));
	printf("%lld\n",ans);return 0;
}