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>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

ll gcd(ll n, ll m) {
    if (n < m) swap(n, m);
    while (m != 0) {
        ll r = n % m;
        n = m;
        m = r;
    }
    return n;
}

ll modinv(int n, int p) {
    int m = p, y = 0, v = 1;
    while (1) {
        int q = m / n;
        int r = m % n;
        if (r == 0) return v < 0 ? v + p : v;
        y -= v * q;
        swap(y, v);
        m = n;
        n = r;
    }
}

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

int main() {
    ll n;
    cin >> n;

    if (n == 1) {
        cout << 1 << endl;
        exit(0);
    } else if (n == 2) {
        cout << 3 << endl;
        exit(0);
    }

    n *= 2;

    ll r = n - 1;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ll j = n / i;
            if (gcd(i, j) == 1) {
                ll a, b;
                extgcd(i, j, a, b);
                if (a == 0 || b == 0) continue;
                if (a < 0) {
                    a *= -1;
                    r = min(r, a * i);
                } else {
                    b *= -1;
                    r = min(r, b * j);
                }
            }
        }
    }

    cout << r << endl;

    return 0;
}