#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef __int128 LL;
typedef unsigned long long ULL;
#define SZ(x) ((int)((x).size()))

// Overloading of the operator << for __int128 type.
ostream& operator <<(ostream& out, __int128 x) {
    static short int digits[41];
    if (x == 0) {
        out << '0';
        return out;
    }
    if (x < 0) {
        out << '-';
        x = -x;
    }
    int length = 0;
    for (; x > 0; x /= 10) {
        digits[length] = x % 10;
        length++;
    }
    for (int i = length - 1; i >= 0; i--) out << digits[i];
    return out;
}


// Computes the inverse of n modulo m.
// Precondition: n >= 0, m > 0 and gcd(n, m) == 1.
// The returned value satisfies 0 <= x < m (Inverse(0, 1) = 0).
// ACHTUNG: It must hold max(m, n) < 2**31 to avoid integer overflow.
LL Inverse(LL n, LL m) {
    n %= m;
    if (n <= 1) return n; // Handles properly (n = 0, m = 1).
    return m - ((m * Inverse(m, n) - 1) / n);
}

template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
    bool done_something = false;
    stringstream res;
    res << "[";
    for (; begin_iter != end_iter and counter; ++begin_iter) {
        done_something = true;
        counter--;
        res << *begin_iter << ", ";
    }
    string str = res.str();
    if (done_something) {
        str.pop_back();
        str.pop_back();
    }
    str += "]";
    return str;
}

vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
    vector<int> ord(size);
    for (int i = 0; i < size; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), compare);
    return ord;
}

template <typename T>
bool MinPlace(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool MaxPlace(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        out << v[i];
        if (i != (int)v.size()-1) out << ", ";
    }
    out << "]";
    return out;
}

template<class TH>
void _dbg(const char* name, TH val){
    clog << name << ": " << val << endl;
}
template<class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
    while(*names != ',') clog << *names++;
    clog << ": " << curr_val << ", ";
    _dbg(names+1, vals...);
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file

    #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
    #define dbg_arr(x, len) clog << #x << ": " << print_iterable(x, x+len, -1) << endl;
#else
    #define dbg(...)
    #define dbg_arr(x, len)
#endif

///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////

// Computes (a*b) % mod avoiding integer overflow.
// Assumption: mod < 2**61.
ULL BigModMultiplication(ULL a, ULL b, ULL mod) {
    a %= mod, b %= mod;
    return ((__int128) a)*((__int128) b) % mod;
    ULL res = 0;
    while (a > 0) {
        if (a & 1) res += b;
        a >>= 1;
        b <<= 1;
        b %= mod;
        res %= mod;
    }
    return res;
}

// Computes (x**e) % mod avoiding integer overflow.
// Assumption: mod < 2**61.
ULL BigModPower(ULL x, ULL e, ULL mod) {
    ULL res = 1;
    while (e) {
        if (e & 1) res = BigModMultiplication(res, x, mod);
        e >>= 1;
        x = BigModMultiplication(x, x, mod);
    }
    return res;
}

// Whether p is prime.
// It implements Miller-Rabin algorithm (with some optimizations).
// Assumptions:   p >= 0.
//               p <= 2**61.
// In order to support p > 1e9 it uses BigModMultiplication and BigModPower,
// hence it is very slow.
bool IsPrime(ULL p) {
    if (p <= 1) return false;
    static const ULL first_primes[21] = {2, 3, 5, 7, 11, 13, 17, 19, 23,
                                         29, 31, 37, 41, 43, 47, 53, 59,
                                         61, 67, 71, 73};
    // Checking the divisibility by the first 15 primes.
    // Not necessary in our case!
    // for (int i = 0; i < 15; i++) {
        // if (p % first_primes[i]== 0) {
            // if (p == first_primes[i]) return true;
            // return false;
        // }
    // }

    ULL x = p-1;
    int e = 0;
    while (x % 2 == 0) {
        x = x >> 1;
        e++;
    }

    static const map<ULL, int> primes_to_check_table = {
        {2047, 1}, {1373653, 2}, {25326001, 3}, {3215031751ULL, 4},
        {2152302898747ULL, 5}, {3474749660383ULL, 6}, {341550071728321ULL, 7},
        {3825123056546413051ULL, 9}, {1ll<<62, 21}};
    int primes_to_check_num = primes_to_check_table.upper_bound(p)->second;

    for (int i = 0; i < primes_to_check_num; i++) {
        bool composite = true;
        ULL temp = BigModPower(first_primes[i], x, p);
        if (temp != 1 and temp != p-1) {
            for (int k = 0; k < e; k++) {
                temp = BigModMultiplication(temp, temp, p);
                if (temp == p-1) {
                    composite = false;
                    break;
                }
            }
        }
        else composite = false;
        if (composite) return false;
    }
    return(true);
}

vector<pair<LL, int>> join_fact(const vector<pair<LL,int>>& f1, const vector<pair<LL,int>>& f2) {
    vector<pair<LL, int>> f;
    int it1 = 0, it2 = 0;
    while (it1 < SZ(f1) or it2 < SZ(f2)) {
        if (it1 == SZ(f1) or (it2 < SZ(f2) and f1[it1] > f2[it2])) {
            if (!f.empty() and f.back().first == f2[it2].first) {
                f.back().second += f2[it2].second;
            } else f.push_back(f2[it2]);
            it2++;
        } else {
            if (!f.empty() and f.back().first == f1[it1].first) {
                f.back().second += f1[it1].second;
            } else f.push_back(f1[it1]);
            it1++;
        }
    }
    return f;
}

// Implementation of Pollard-Rho algorithm to find a nontrivial factor
// of n. As cycle-detection method, Brent's algorithm is used.
// The expected running time is O(sqrt(p)*log(n)) where p is the smallest prime
// factor of n.
// Assumption: n > 1 is not a prime.
ULL FindFactor(ULL n) {
    while (1) {
        ULL x = rand();
        ULL y = x;
        auto next_x = [&x, n]() { x = (BigModMultiplication(x, x, n)+1)%n; };
        ULL res = 1;
        for (int sz = 2; res == 1; sz<<=1) {
            for (int i = 0; i < sz && res == 1; i++) {
                next_x();
                res = __gcd(n+x-y, n);
                if (res != 1 and res != n) {
                    return res;
                }
            }
            y = x;
        }
    }
}

const int MAXN = 1e5;
int ppp[MAXN];

vector<pair<LL, int>> factor_internal(LL n) {
    if (n < MAXN) {
        vector<pair<LL, int>> fact;
        while (n != 1) {
            LL p = ppp[n];
            n /= p;
            int e = 1;
            while (n%p == 0) n /= p, e++;
            fact.push_back({p, e});
        }
        return fact;
    }
    if (IsPrime(n)) return {{n, 1}};
    LL m = FindFactor(n);
    assert(1 < m and m < n and n%m == 0);
    return join_fact(factor_internal(m), factor_internal(n/m));
}

vector<pair<LL, int>> factor(LL n) {
    static const vector<LL> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23,
                                      29, 31, 37, 41, 43, 47, 53, 59,
                                      61, 67, 71, 73};
    vector<pair<LL,int>> fact;
    
    for (LL p: primes) {
        if (n%p == 0) {
            int e = 1;
            n /= p;
            while (n%p == 0) n /= p, e++;
            fact.push_back({p, e});
        }
    }
    if (n != 1) return join_fact(fact, factor_internal(n));
    return fact;
}


// Returns the largest number m that divides n such that it has only primes
// that divide d.
// The complexity is logarithmic (computing efficiently gcd(d^100,n)).
//
// Assumptions: d | n
//              d < 1<<31.
//              "returned value" < 1<<31 (true if n < 1<<31)
LL CommonPart(LL d, LL n) {
    LL x = d;
    LL y = 1;
    while (x != y) {
        y = x;
        x = __gcd(x*x, n);
    }
    return x;
}

// Returns an x (with absolute value below mn) such that m|x-a and n|x-b.
//
// Assumptions: m, n coprimes.
//              mn, n² < 1<<62
//
// ACHTUNG: The returned value might be negative.
LL CrtInternal(LL a, LL m, LL b, LL n) {
    a %= m, b %= n;
    LL inv = Inverse(m, n);
    LL x = a + m * (inv*(b-a) % n);
    return x%(m*n);
}

// Returns the solution to the given system of modular equation.
// The system is given as a vector of pair <value, modulo>.
// The result is a pair <value, modulo> with 0 <= value < modulo.
// If there is no solution the returned pair is {0, 0}.
//
// Assumptions: The lcm of the modulos must be below 2**31.
//
// ACHTUNG: To handle modulos with lcm > 2**31, use __int128.
pair<LL, LL> SolveRemainderSystem(const vector<pair<LL, LL>>& system) {
    if (system.empty()) return {0, 1};
    LL m = system[0].second;
    LL a = system[0].first % m;
    
    for (int i = 1; i < (int)system.size(); i++) {
        LL n = system[i].second;
        LL b = system[i].first % n;

        LL g = __gcd(m, n);
        if (g != 1) {
            if ((a-b)%g != 0) return {0, 0};
            LL m2 = CommonPart(m/g, m); // a
            LL n2 = CommonPart(n/g, n); // b
            LL z = g / (__gcd(g, m2) * __gcd(g, n2));
            a = CrtInternal(CrtInternal(a%m2, m2, b%n2, n2), m2*n2, a%z, z);
            m = m2*n2*z;
        } else {
            a = CrtInternal(a, m, b, n);
            m = m * n;
        }
    }
    if (a < 0) a += m;
    return {a, m};
}

int main() {
    for (int p = 2; p < MAXN; p++) {
        if (ppp[p]) continue;
        for (int i = p; i < MAXN; i+=p) if (ppp[i] == 0) ppp[i] = p;
    }

    
    long long N;
    cin >> N;
    N *= 2;

    auto fact = factor(N);

    int E = fact.size();
    vector<LL> prime_powers(E);
    for (int i = 0; i < E; i++) {
        LL pot = 1;
        for (int j = 0; j < fact[i].second; j++) pot *= fact[i].first;
        prime_powers[i] = pot;
    }

    LL ans = N;
    for (int bb = 0; bb < 1<<E; bb++) {
        vector<pair<LL,LL>> vec(E);
        for (int i = 0; i < E; i++) {
            if (bb&(1<<i)) vec[i] = {0, prime_powers[i]};
            else vec[i] = {prime_powers[i]-1, prime_powers[i]};
        }
        auto sol = SolveRemainderSystem(vec);
        if (sol.first == 0) sol.first += sol.second;
        ans = min(sol.first, ans);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4044