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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v){
    if(v.empty()){
        os<<"{ }";
        return os;
    }
    os<<"{"<<v.front();
    for(auto itr=++v.begin();itr!=v.end();itr++){
        os<<", "<<*itr;
    }
    os<<"}";
    return os;
}

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1; y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}

int main(){
    ll n; cin>>n;
    map<ll,int> mp;
    ll N=n;
    for(ll i=2;i*i<=N;i++){
        while(N%i==0){
            mp[i]++;
            N/=i;
        }
    }
    if(N>1) mp[N]++;
    mp[2]++;
    int prcnt=mp.size();
    vector<ll> pr(prcnt,1);
    int idx=0;
    for(auto p:mp){
        rep(i,p.second) pr[idx]*=p.first;
        idx++;
    }
    ll ans=INF;
    rep(i,(1<<prcnt)){
        ll a=1,b=1,x,y;
        rep(j,prcnt){
            if(i&(1<<j)) a*=pr[j];
            else b*=pr[j];
        }
        exgcd(a,b,x,y);
        x=(b+x%b)%b;
        y=(a+y%a)%a;
        if(min(x,y)==0){
            ans=min(max(a,b)-1,ans);
            continue;
        }
        ans=min(a*x-1,ans);
        ans=min(b*y-1,ans);
        //cout<<x<<" "<<y<<endl;
    }
    cout<<ans<<endl;
}