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>
#define int long long
using namespace std;


int n,p[100],cnt,ans=1ll<<60;


int exgcd(int a,int b,int &x,int &y)
{
	if(!b)	{x=1;y=10;return a;}
	int d=exgcd(b,a%b,x,y);
	int z=y;y=x-a/b*y;x=z;
	return d;
}

void dfs(int pos,int k1,int k2)
{
	if(pos==cnt+1)
	{
		int x,y;
		exgcd(k1,k2,x,y);
//		cout<<x*k1<<' '<<y*k2<<endl;
//		cout<<x<<' '<<y<<' '<<k1<<' '<<k2<<endl;
//		if(x<0)	return;
		x=(x%k2+k2)%k2;
//		cout<<x<<endl;
		if(x==0)	x=k2;
		if(x==1&&k1==1)	return; 
		ans=min(ans,x*k1-1);
		return;
	}
	dfs(pos+1,k1*p[pos],k2);
	dfs(pos+1,k1,k2*p[pos]);
}


signed main()
{
	cin>>n;
	int u=n*2;
	for(int i=2;i<=min(n,40000000ll);i++)
	{
		int now=1;
		while(u%i==0)
		{
			now*=i;
			u/=i;
		}
		if(now!=1)	p[++cnt]=now;	
	}
	if(u!=1)	p[++cnt]=u;
	dfs(1,1,1);		//µ±Ç°µÄµÚÒ»¸öÖÊÊý  µ±Ç°µÄµÚ¶þ¸öÖÊÊý 
	cout<<ans<<endl;
} 