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 <iostream>
#include <vector>
using namespace std;
typedef long long ll;

long long ext_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long x2, y2;
    long long d = ext_gcd(b, a%b, x2, y2);
    x = y2;
    y = x2 - (a / b)*y2;
    return d;
}

int main()
{
    ll n;
    cin >> n;
    if(n == 1){
        cout << 1 << endl;
        return 0;
    }
    ll m = n;
    vector<ll> v;
    for(ll i = 2; i * i <= n; i++){
        if(m % i == 0){
            ll s = 1;
            while(m % i == 0){
                m /= i;
                s *= i;
            }
            v.push_back(s);
        }
    }
    if(m > 1) v.push_back(m);
    int k = v.size();
    ll ans = n - 1;
    if(v[0] % 2 == 0){
        ans = n * 2 - 1;
    }
    for(int i = 0; i < (1 << k); i++){
        ll l = 1, r = 1;
        for(int j = 0; j < k; j++){
            if((i >> j) & 1) l *= v[j];
            else r *= v[j];
        }
        if(l > r){
            if(l % 2 == 0) l *= 2;
            if(r % 2 == 0) r *= 2;
            ll x = 1, y = 0;
            ext_gcd(l, r, x, y);
            x = abs(x);
            y = abs(y);
            if(x == 0 || y == 0){
                x += r;
                y += l;
            }
            ans = min(ans, min(l * x, r * y));
        }
    }
    cout << ans << endl;
}
