#include <bits/stdc++.h>

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int _i=(first);_i<(last);++_i){cout<<#a<<"["<<_i<<"] = "<<(a)[_i]<<endl;}
#define PRINTI(a,i)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<#i<<"] = "<<#a<<"["<<(i)<<"] = "<<(a)[i]<<endl;
#define dprintf(...) printf(__VA_ARGS__)
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#define PRINTI(a,i)
#define dprintf(...)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

template <class T, class U>
std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}
 
template <class T>
std::ostream& operator<<(std::ostream &os, const std::vector<T> &v) {
    os << "[";
	for (int i = 0; i < v.size(); ++i) {
        if (i) {
            if (i % 5 == 0) {
                os << ",\n ";
            } else {
                os << ", ";
            }
        }
		os << v[i];
	}
	os << "]";
	return os;
}

template <class T>
using vec2 = vector<vector<T>>;

template <class T>
using vec3 = vector<vector<vector<T>>>;

template <class T>
vec2<T> vec2_init(int n0, int n1, T x = 0) {
    return vec2<T>(n0, vector<T>(n1, x));
}

template <class T>
vec3<T> vec3_init(int n0, int n1, int n2, T x = 0) {
    return vec3<T>(n0, vec2_init(n1, n2, x));
}

/*
 *           U P
 *           - x
 *            ^
 *            |
 * LEFT -y <--+--> +y RIGHT
 *            |
 *            v
 *           + x
 *         D O W N
 */

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

enum {
    DOWN,
    RIGHT,
    UP,
    LEFT,
};

constexpr double inf = numeric_limits<double>::infinity();

template <class SignedInteger>
unsigned long long gcd_extended(unsigned long long a, unsigned long long b, SignedInteger &x, SignedInteger &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    SignedInteger x0, y0;
    unsigned long long d = gcd_extended(b, a % b, x0, y0);
    x = y0;
    y = x0 - a / b * y0;
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    ll N2 = N * 2;

    ll result = 2 * N;

    vector<ll> factors;

    ll sqrt2N = sqrt(N2) + 0.5;

    FOR(D, 2, sqrt2N + 1) {
        ll pe = 1;
        while (N2 % D == 0) {
            N2 /= D;
            pe *= D;
        }
        if (pe > 1) {
            factors.push_back(pe);
        }
    }
    if (N2 > 1) {
        factors.push_back(N2);
    }

    int L = factors.size();
    REP(bit, 1 << L) {
        ll D = 1;
        ll D_ = 1;
        REP(i, L) {
            if ((bit >> i) & 1) {
                D *= factors[i];
            } else {
                D_ *= factors[i];
            }
        }
        PRINT(D);
        PRINT(D_);
        ll mQ, R;
        ll gcd = gcd_extended(D, D_, mQ, R);
        if (gcd != 1) {
            continue;
        }
        if (mQ >= 0) {
            mQ %= D_;
            while (mQ >= 0) {
                mQ -= D_;
            }
        }
        ll Q = -mQ;
        ll k = D * Q;
        amin(result, k);
    }
    cout << result << endl;

    /*
    FOR(D, 1, N2 + 1) {
        if (N2 % D != 0) {
            continue;
        }
        PRINT("");
        function<void(ll, ll)> f = [&](ll d, ll d_) {
            ll mQ, R;
            ll gcd = gcd_extended(d, d_, mQ, R);
            if (gcd != 1) {
                return;
            }
            if (mQ >= 0) {
                mQ %= d_;
                while (mQ >= 0) {
                    mQ -= d_;
                }
            }

            ll Q = -mQ;
            ll k = d * Q;
            amin(result, k);
        };
        ll D_ = N2 / D;
        f(D, D_);
        f(D_, D);
    }
    */

    return 0;
}


Measured memory_bytes: 3676