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 debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> p2;
#define sz(a) ll(a.size())
vector<ll> g,v;
ll n,res,hell=pow(10,18);
ll gcd(ll a,ll b,ll& x,ll& y) {
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll d=gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return d;
}
ll inv(ll a,ll m){
	ll x,y;
	gcd(a,m,x,y);
	x=(x%m+m)%m;
	return x;
}
void f(ll cnt){
	if(cnt==sz(v)){
		ll j=0,x=1,y=1;
		for(ll i=0;i<sz(v);i++){
			if(j<sz(g)&&g[j]==i){
				x*=v[i];
				j++;
				continue;
			}
			y*=v[i];
		}
		ll val=inv(x,y),cnt=0;
		while(cnt<5){
			if(val>hell/x){
				cnt=100;
				break;
			}
			ll jok=(val*x-1)/y;
			if(val*x>1&&(val%2==0||jok%2==0))
				break;
			val+=y;
			cnt++;
		}
		if(cnt<5)
			res=min(res,val*x-1);
		return;
	}
	f(cnt+1);
	g.push_back(cnt);
	f(cnt+1);
	g.pop_back();
}
void solve(){
	cin>>n;
	res=hell;
	for(ll i=2;i*i<=n;i++)
		if(n%i==0){
			v.push_back(1);
			while(n%i==0){
				v.back()*=i;
				n/=i;
			}
		}
	if(n>1)
		v.push_back(n);
	f(0);
	cout<<res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif
    clock_t z=clock();
    ll qc=1;
    //cin>>qc;
    for(ll i=1;i<=qc;i++){
        solve();
    }
    debug("Total Time:%.4Lf\n",(ld)(clock()-z)/CLOCKS_PER_SEC);
}
