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;
int const nax = 3e5 + 10;
int64_t n;
int64_t ans = 1e18;


int64_t ex_gcd(int64_t a, int64_t b, int64_t& x, int64_t& y) {
    x = 1, y = 0;
    int64_t x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int64_t q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}


void brute(int64_t x, int64_t y) {
    int64_t foo, bar;
    if (ex_gcd(x, y, foo, bar) != 1) return ;
    int64_t real_foo = foo * x;
    int64_t real_bar = -y * bar;
    if (real_bar > 0) ans = min(ans, real_bar);
    else {
        int64_t need = 1 - real_bar;
        int64_t add = (need + n - 1) / n;
        real_bar += add * n;
        ans = min(ans, real_bar);
    }
}

int main() {

    cin >> n;
    n <<= 1;

    for (int64_t i = 1 ; i * i <= n ; ++ i)
        if (n % i == 0) brute(i, n / i), brute(n / i, i);

    cout << ans << '\n';
}
/*
    Why not Ventuswill?
*/
