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;
typedef long long ll;
ll ans = LLONG_MAX;
vector<ll> vp;
void exgcd(ll a, ll &x, ll b, ll&y, ll&g)
{
    if (b) {
        exgcd(b, y, a % b, x, g);
        y -= a/b*x;
    } else {
        x = 1;
        y = 0;
        g = a;
    }
}
void solve(ll a, ll b)
{
    ll x0, y0, g;
    exgcd(a, x0, b, y0, g);
    ll t = 2 - a * x0;
    if (t < 0)
        t /= a * b;
    else
        t = (t + a * b - 1) / (a * b);
    ll x = x0 + t * b;
    ll k = x * a - 1;
    assert(k > 0);
    //cerr << "a, b, k " << a << ' ' << b << ' ' << k << endl;
    ans = min(ans, k);
}
void dfs(int i, ll a = 1, ll b = 1)
{
    if (i == vp.size()) {
        solve(a, b);
        return;
    }
    dfs(i + 1, a * vp[i], b);
    dfs(i + 1, a, b * vp[i]);
}
int main()
{
    ll n;
    cin >> n;
    if (n == 1) {
        cout << "1\n";
        return 0;
    }
    for (ll i = 2; i * i <= n; ++i) {
        ll p = 1;
        while (n % i == 0) {
            n /= i;
            p *= i;
        }
        if (p > 1) {
            vp.emplace_back(p * (p % 2 == 0 ? 2 : 1));
        }
    }
    if (n > 1)
        vp.emplace_back(n);
    dfs(0);
    cout << ans << endl;
}
