#include <bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
//typedef __int128_t LL;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
mt19937 rnd;

std::ostream& operator<<(std::ostream& dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char* d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

struct Equ {
    ll r, mod;
};

ll __lcm(ll a, ll b) {
    return a / __gcd(a, b) * b;
}

ll gcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

bool find_any_solution(ll a, ll b, ll c, ll& x0, ll& y0) {
    ll A = a, B = b;
    if (A < 0) A *= -1;
    if (B < 0) B *= -1;
    ll g = gcd(A, B, x0, y0);
    if (c % g != 0) return 0;
    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 *= -1;
    if (b < 0) y0 *= -1;
    return 1;
}

ll CRT_2(Equ p, Equ q) {
    ll x, y;
    if (!find_any_solution(p.mod, -q.mod, q.r - p.r, x, y)) {
        return -1;
    }
    ll X = p.mod * x + p.r;
    ll tot_mod = __lcm(p.mod, q.mod);
    X = (X % tot_mod + tot_mod) % tot_mod;
    return X;
}

Equ merge(Equ p, Equ q) {
    return {CRT_2(p, q), __lcm(p.mod, q.mod)};
}

ll CRT(vector<Equ> vec) {
    Equ cur = vec[0];
    for (int i = 1; i < vec.size(); i++) {
        cur = merge(cur, vec[i]);
        if (cur.r == -1) {
            return -1;
        }
    }
    return cur.r;
}

ll calc(ll a, ll b) {
    ll res = -1;
    if ((a * b) & 1) {
        res = CRT_2({0, a}, {b - 1, b});
    }
    else {
        if (!(a & 1)) {
            res = CRT_2({0, 2 * a}, {b - 1, b});
        }
        else {
            res = CRT_2({0, a}, {2 * b - 1, 2 * b});
        }
    }
    if (!res) {
        res = a * b;
    }
    return res;
}

ll solve(ll n) {
    ll ans = 1e18 + 10;
    for (ll a = 1; a * a <= n; a++) {
        ll b = n / a;
        if (n % a == 0) {
            if (__gcd(a, b) == 1) {
                ll k = calc(a, b);
                if (k != -1) {
                    ans = min(ans, k);
                }
                k = calc(b, a);
                if (k != -1) {
                    ans = min(ans, k);
                }
            }
        }
    }
    return ans;
}

ll slow(ll n) {
    for (ll k = 1; k <= 5 * n; k++) {
        if ((k * (k + 1) / 2) % n == 0) {
            return k;
        }
    }
    return -1;
}

void stress() {
    while (1) {
        ll n = rnd() % 1000000000 + 1;
        ll ans = solve(n);
        ll res = slow(n);
        if (ans != res) {
            cout << "Wrong answer" << endl;
            cout << n << endl;
            cout << ans << " " << res << endl;
            break;
        }
        else {
            cout << "OK" << endl;
        }
    }
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    long long nn;
    cin >> nn;
    ll n = nn;
    cout << solve(n) << "\n";

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 3664