#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
ll m;
int k;
mt19937_64 rnd(228);

const int BUBEN = (int) 1e6 + 228;
const int BUBEN2 = 15;

long long multModulo(long long a, long long b, long long m) {
    long long q = (long long) ((long double) a * (long double) b / (long double) m);
    long long r = a * b - q * m;
    while (r < 0) r += m;
    while (r >= m) r -= m;
    return r;
}

ll sumModulo(ll a, ll b, ll mod) {
    ll s = a + b;
    if (s >= mod) s -= mod;
    return s;
}

ll powModulo(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b & 1) return multModulo(a, powModulo(a, b - 1, mod), mod);
    ll res = powModulo(a, b / 2, mod);
    return multModulo(res, res, mod);
}

ll pollard_rho(ll n) {
    ll y = rnd() % (n - 1) + 1;
    ll c = rnd() % (n - 1) + 1;
    ll m = rnd() % (n - 1) + 1;
    ll g = 1;
    ll r = 1;
    ll q = 1;
    ll x = 0;
    ll ys = 0;
    ll k = 0;
    while (g == 1) {
        x = y;
        for (int i = 0; i < r; i++) {
            y = sumModulo(multModulo(y, y, n), c, n);
            k = 0;
        }
        while (k < r && g == 1) {
            ys = y;
            for (int i = 0; i < min(m, r - k); i++) {
                y = sumModulo(multModulo(y, y, n), c, n);
                q = multModulo(q, abs(x - y), n);
                g = __gcd(q, n);
            }
            k = k + m;
        }
        r *= 2;
    }
    if (g == n) {
        while (true) {
            ys = sumModulo(multModulo(ys, ys, n), c, n);
            g = __gcd(abs(x - ys), n);
            if (g > 1) break;
        }
    }
    return g;
}

bool is_prime(ll n) {
    if (n == 2 || n == 3 || n == 5 || n == 7) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) {
        return false;
    }
    ll d = n - 1;
    int r = 0;
    // can add
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    for (int j = 0; j < BUBEN2; j++) {
        ll a = rnd() % (n - 3) + 2;
        ll x = powModulo(a, d, n);
        if (x == 1 || x == n - 1) {
            continue;
        }
        for (int it = 0; it < r - 1; it++) {
            x = multModulo(x, x, n);
            if (x == n - 1) {
                break;
            }
        }
        if (x != (n - 1)) {
            return false;
        }
    }
    return true;
}

int lp[BUBEN];
vector<int> small_primes;

void init() {
    for (int i = 2; i < BUBEN; i++) {
        if (lp[i] == 0) {
            lp[i] = i;
            if (i < BUBEN) small_primes.push_back(i);
            for (int j = 2 * i; j < BUBEN; j += i) lp[j] = i;
        }
    }
}

vector<pair<ll, int >> get_fact(ll n) {
    vector<pair<ll, int> > ans;
    if (n < BUBEN) {
        // factorize
        while (n > 1) {
            int p = lp[n];
            int ex = 0;
            while (n % p == 0) {
                n /= p;
                ex++;
            }
            ans.emplace_back(p, ex);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
    if (n == 1) return {};
    ll fact = 0;
    for (ll v : small_primes) {
        if (n % v == 0) {
            fact = v;
            break;
        }
    }
    if (fact != 0) {
        int ex = 0;
        while (n % fact == 0) {
            n /= fact;
            ex++;
        }
        ans.emplace_back(fact, ex);
        auto ans2 = get_fact(n);
        for (auto it : ans2) ans.push_back(it);
        return ans;
    }

    if (is_prime(n)) {
        ans.emplace_back(n, 1);
        return ans;
    }
    if (fact == 0) {
        fact = 1;
        while (fact == 1 || fact == n) fact = pollard_rho(n);
    }
    auto cur_ans = get_fact(fact);
    n /= fact;
    for (auto &t : cur_ans) {
        ll x = t.first;
        int y = t.second;
        if (n % x == 0) {
            while (n % x == 0) {
                n /= x;
                y++;
            }
        }
        ans.emplace_back(x, y);
    }
    if (n > 1) {
        auto ans2 = get_fact(n);
        for (auto it : ans2) ans.push_back(it);
        return ans;
    }
    sort(ans.begin(), ans.end());
    return ans;
}
ll do_gcd(ll a, ll b, ll& x, ll& y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll p = b / a;
    ll g = do_gcd(b - p * a, a, y, x);
    x -= p * y;
    return g;
}
ll getInv(ll a, ll M) {
    ll c1, c2;
    ll d = do_gcd(a, M, c1, c2);
    assert(d == 1);
    c1 %= M;
    if (c1 < 0) c1 += M;
    return c1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    init();
    ll n;
    cin >> n;
    n *= 2;
    auto it = get_fact(n);
    ll best = n;
    for (int mask = 0; mask < (1 << it.size()); mask++) {
        ll mod1 = 1;
        ll mod2 = 1;
        for (int i = 0; i < it.size(); i++) {
            ll p = 1;
            for (int j = 0; j < it[i].second; j++) p *= it[i].first;
            if (mask & (1 << i)) {
                mod1 *= p;
            }
            else {
                mod2 *= p;
            }
        }
        ll f = getInv(mod2, mod1);
        if (f == 0) f += mod1;
        if (f * mod2 == 1) {
            f += mod1;
        }
        best = min(best, f * mod2 - 1);
    }
    cout << best;
    return 0;
}

Measured memory_bytes: 7740