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;

int m;
long long n,ans;
int p[105],q[105];
long long mu[105];

void exgcd(long long x,long long y,long long &a,long long &b){
	if(y==0){
		a=1;
		b=0;
	}else{
		exgcd(y,x%y,a,b);
		long long c=a;
		a=b;
		b=c-x/y*b;
	}
}

void dfs(int x,long long mul){
	if(x==m){
		if(mul!=1ll&&mul!=n){
			long long r1,r2;
			exgcd(mul,n/mul,r1,r2);
			ans=min(ans,-1ll*min(mul*r1,n/mul*r2));
		}
		return;
	}
	dfs(x+1,mul);
	dfs(x+1,mul*mu[x+1]);
}

int main(){
	scanf("%lld",&n);
	if(n==1ll){
		puts("1");
		return 0;
	}
	n*=2;
	ans=n;
	long long rn=n;
	for(long long i=2ll;i*i<=rn;i++) if(rn%i==0ll){
		p[++m]=i;
		mu[m]=1ll;
		while(rn%i==0ll){
			rn/=i;
			q[m]++;
			mu[m]*=i;
		}
	}
	if(rn!=0ll){
		p[++m]=rn;
		mu[m]=rn;
		q[m]=1;
	}
	dfs(0,1ll);
	printf("%lld\n",ans);
	return 0;
}