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;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x,T y){x<y?x=y:T();}
template <typename T> void chkmin(T &x,T y){x>y?x=y:T();}
template <typename T> void readint(T &x)
{
	x=0;int f=1;char c;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-'0';
	x*=f;
}
const int MOD=998244353;
inline int dmy(int x){return x>=MOD?x-MOD:x;}
inline void inc(int &x,int y){x=dmy(x+y);}
int qmi(int x,int y)
{
	int ans=1;
	for(;y;y>>=1,x=1ll*x*x%MOD)
		if(y&1)ans=1ll*ans*x%MOD;
	return ans;
}
const int MAXK=105;

ll n;
int k;
ll p[MAXK];
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-(a/b)*y;
}

int main()
{
	#ifdef LOCAL
	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
	#endif
	readint(n);
	if(n==1)return 0*printf("1\n");
	n<<=1;
	ll u=n;
	for(ll i=2;i*i<=u;++i)
	{
		if(u%i)continue;
		ll x=1;
		while(!(u%i))u/=i,x*=i;
		p[k++]=x;
	}
	if(u>1)p[k++]=u;
	ll ans=n;
	for(int s=0;s<(1<<k);++s)
	{
		ll a=1;
		for(int i=0;i<k;++i)
			if(s&(1<<i))a*=p[i];
		ll b=n/a,x,y;
		exgcd(a,b,x,y);
		x=(x%b+b-1)%b+1;
		y=(a*x-1)/b;
		if(!y)y+=a,x-=b;
		chkmin(ans,b*y);
	}
	printf("%lld\n",ans);
	return 0;
}