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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
template<typename T>
T extgcd(T a,T b,T&x,T&y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	T q=a/b;
	T g=extgcd(b,a-q*b,y,x);
	y-=q*x;
	return g;
}
long N,ans;
vector<pair<long,int> >X;
void dfs(int id,long x)
{
	if(id<X.size())
	{
		dfs(id+1,x);
		for(int i=0;i<X[id].second;i++)
		{
			x*=X[id].first;
		}
		dfs(id+1,x);
		return;
	}
	long y=2*N/x;
	long l,m;
	long g=extgcd(x,y,m,l);
	m=-m;
	if(m>0&&(ans+m-1)/m>x)ans=min(ans,m*x);
	return;
}
int main()
{
	cin>>N;
	if(N==1)
	{
		cout<<1<<endl;
		return 0;
	}
	ans=2*N-1;
	if(N%2==1)ans=N-1;
	long T=2*N;
	for(long i=2;i*i<=T;i++)
	{
		if(T%i==0)
		{
			X.push_back(make_pair(i,0));
			while(T%i==0)
			{
				X.back().second++;
				T/=i;
			}
		}
	}
	if(T>1)X.push_back(make_pair(T,1));
	dfs(0,1L);
	cout<<ans<<endl;
}
