#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
template<typename T> using V = vector<T>;
template<typename T> using P = pair<T, T>;
using ll = long long;
using ld = long double;
using Vi = V<int>;  using VVi = V<Vi>;
using Vl = V<ll>;   using VVl = V<Vl>;
using Vd = V<ld>;   using VVd = V<Vd>;
using Vb = V<bool>; using VVb = V<Vb>;
using Pi = P<int>;
using Pl = P<ll>;
using Pd = P<ld>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> inline int sz(T &x) { return x.size(); }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline ll cDiv(const ll x, const ll y) { return (x+y-1) / y; } // ceil(x/y)
inline int fLog2(const ll x) { assert(x > 0); return 63-__builtin_clzll(x); } // floor(log2(x))
inline int cLog2(const ll x) { assert(x > 0); return (x == 1) ? 0 : 64-__builtin_clzll(x-1); } // ceil(log2(x))
inline int popcount(const ll x) { return __builtin_popcountll(x); }
inline void fail() { cout << -1 << '\n'; exit(0); }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
// const int INF  = 1<<30;
// const ll INFll = 1ll<<60;
// const ld EPS   = 1e-10;
// const ld PI    = acos(-1.0);
// const int MOD  = int(1e9)+7;
// const int MOD  = 998244353;






struct Factorize {
private:
    unsigned long long modmul(unsigned long long a, unsigned long long b, unsigned long long M) {
        long long ret = a * b - M * (unsigned long long)(1.L / M * a * b);
        return ret + M * (ret < 0) - M * (ret >= (long long)M);
    }
    
    unsigned long long modpow(unsigned long long b, unsigned long long e, unsigned long long mod) {
        unsigned long long ans = 1;
        for (; e; b = modmul(b, b, mod), e /= 2)
            if (e & 1) ans = modmul(ans, b, mod);
        return ans;
    }
    
    bool is_prime(unsigned long long n) {
        if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
        unsigned long long A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        unsigned long long s = __builtin_ctzll(n-1), d = n >> s;
        for (unsigned long long a : A) {
            unsigned long long p = modpow(a%n, d, n), i = s;
            while (p != 1 && p != n - 1 && a % n && i--)
                p = modmul(p, p, n);
            if (p != n-1 && i != s) return 0;
        }
        return 1;
    }
    
    unsigned long long pollard(unsigned long long n) {
        auto f = [&](unsigned long long x) { return modmul(x, x, n) + 1; };
        unsigned long long x = 0, y = 0, t = 0, prd = 2, i = 1, q;
        while (t++ % 40 || __gcd(prd, n) == 1) {
            if (x == y) x = ++i, y = f(x);
            if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
            x = f(x), y = f(f(y));
        }
        return __gcd(prd, n);
    }
    
    vector<unsigned long long> factor(unsigned long long n) {
        if (n == 1) return {};
        if (is_prime(n)) return {n};
        unsigned long long x = pollard(n);
        auto l = factor(x), r = factor(n / x);
        l.insert(l.end(), r.begin(), r.end());
        return l;
    }
    
public:
    template<typename T>
    vector<T> get_vector(T n, bool sorted = false) {
        auto fac = factor(n);
        vector<T> res(fac.size());
        int idx = 0;
        for(auto &x : fac) res[idx++] = x;
        if (sorted) sort(res.begin(), res.end());
        return res;
    }
    
    template<typename T>
    map<T, int> get_map(T n) {
        auto fac = factor(n);
        map<T, int> res;
        for(auto &x : fac) res[(T)x]++;
        return res;
    }
};


int main() {
  Factorize fac;
  ll n; cin >> n;

  Vl v;
  for (auto [x, y] : fac.get_map(2*n)) {
    v.push_back(1);
    rep(i, y) v.back() *= x;
  }
  sort(all(v));

  int m = sz(v);
  int M = 1<<m;

  ll ans = 2*n;

  rep(S, M) {
    ll d = 1;
    ll e = 1;
    rep(i, m) {
      if (S>>i&1) d *= v[i];
      else e *= v[i];
    }
    auto [y, z] = crt({0, e-1}, {d, e});
    if (y == 0) y += z;
    chmin(ans, y);
  }
  cout << ans << '\n';
}



Measured memory_bytes: 3704