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 <cmath>
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

vector<long long> factor(long long n) {
    vector<long long> fs;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            long long q = 1;
            while (n % p == 0) { n /= p; q *= p; }
            fs.emplace_back(q);
        }
    }
    if (n > 1) fs.emplace_back(n);
    return fs;
}

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

int main() {
    long long n; cin >> n;
    vector<long long> fs = factor(2*n);
    const int m = fs.size();
    long long ans = 2*n - 1;
    for (int s = 1; s < (1<<m) - 1; s++) {
        long long a = 1, b = 1;
        for (int i = 0; i < m; i++) {
            if ((s >> i) & 1) a *= fs[i];
            else b *= fs[i];
        }
        long long x, y;
        assert(extgcd(a, b, x, y) == 1);
        ans = min(ans, min(abs(a * x), abs(b * y)));
    }
    cout << ans << endl;
}
