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 rep(i,n) for (int i=0; i<(n); ++i)
#define per(i,n) for (int i=n-1; i>=0; --i)
#define all(a) a.begin(), a.end()
using namespace std;
using ll = long long;
using P  = pair<int,int>;
using vi = vector<int>;
using vv = vector<vi>;

ll gcd(ll a, ll b){
    if(b>a)swap(a,b);
    while(a%b){
        a %= b;
        swap(a,b);
    }
    return b;
}

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

int main(){
    ll n;
    cin >> n;
    
    n *= 2LL;
    
    vector<ll> d;
    for(ll i=1; i<=n/i; i++){
        if(n%i)continue;
        if(gcd(i, n/i)!=1)continue;
        d.push_back(i);
        d.push_back(n/i);
    }
    ll ans = 2001001001001001;
    for(auto a: d){
        ll b = n/a;
        ll x, y;
        extGCD(a,b,x,y);
        //cout << a << " " << x << " " << y;// << endl;
        //cout << " " << ((-x)%b+b)%b << endl;
        ll k = ((-x)%b+b)%b * a;
        if(k)ans = min(ans, k);
        
    }
    cout << ans << endl;
    return 0;
}