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 fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=33,size=1<<20,inf=2e9;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
    char c=gc; x=0; int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
    while(isdigit(c)) x=x*10+c-'0',c=gc;
    x*=f;
}
template<class o> void qw(o x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
template<class o> void pr1(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar('\n');
}

ll n,ans;
ll p[N],tot,c[1<<16];

void exgcd(ll &x,ll &y,ll a,ll b) {
	if(!a) {x=0; y=1; return ;}
	exgcd(y,x,b%a,a); x -= b/a*y;
}
ll inv(ll a,ll b) {
	a=(2*b-a)%b;
	ll x,y; exgcd(x,y,a,b);
	return (x%b+b)%b;
}

void div(ll x) {
	for(ll i=2;i*i<=x;i++) if(x%i == 0) {
		p[tot]=x;
		while(x%i==0) x/=i;
		p[tot++] /= x;
	}
	if(x>1) p[tot++]=x;
}

int main() {
	qr(n); div(n*2); c[0]=1;
	for(int i=0;i<tot;i++) c[1<<i]=p[i];
	if(n==1) puts("1"),exit(0);
	if(n&1) ans=n-1;
	else ans=n;
	for(int i=1;i+1<(1<<tot);i++) {
		c[i]=c[i&(i-1)]*c[i&(-i)];
		ll x=c[i],y=2*n/x;
		ans=min(ans,x*inv(x,y));
	}
	pr2(ans);
}
