#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#define itrout(x) for(int i=0;i<x.size();i++) {cout << x[i] << (i==x.size()-1 ? "\n" : " ");}
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define debugbit(x, n) cerr << #x << " = " << bitset<n>(x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define debugbit(x, n)
#define itrdebug(x)
#define dassert(...)
#endif
//#define int long long
//using mint = atcoder::modint;

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

class Sieve {
    long long n_;
    vector<long long> sieve_, primes_;

public:
    explicit Sieve(long long n=1): n_(n), sieve_(n + 1) {
        sieve_[0] = sieve_[1] = -1;
        for (long long i = 2; i <= n; ++i) {
            if (sieve_[i]) continue;
            primes_.push_back(i);
            sieve_[i] = i;
            for (long long j = i*i; j <= n; j += i) {
                if (!sieve_[j]) sieve_[j] = i;
            }
        }
    }
    bool isPrime(long long x) {
        assert (n_ * n_ >= x);
        if (n_ >= x) {
            return sieve_[x] == x;
        } else {
            for (const auto prime : primes_) {
                if (x % prime == 0) return false;
            }
            return true;
        }
    }
    vector<long long> getPrimes() {
        return primes_;
    }
    vector<pair<long long, int>> getPrimeFactorList(long long x) {
        assert (n_ * n_ >= x);
        vector<long long> factorList;
        for (int i=(int)primes_.size()-1; i>=0; i--) {
            if (n_ >= x) break;
            while (x % primes_[i] == 0) {
                x /= primes_[i];
                factorList.emplace_back(primes_[i]);
            }
        }
        if (isPrime(x)) {
            factorList.emplace_back(x);
            x /= x;
        }
        assert (n_ >= x);
        while (x != 1) {
            factorList.push_back(sieve_[x]);
            x /= sieve_[x];
        }
        if (factorList.empty()) return {};
        vector<pair<long long, int>> res(1, pair<long long, int>(factorList[0], 0));
        for (long long p : factorList) {
            if (res.back().first == p) {
                res.back().second++;
            } else {
                res.emplace_back(p, 1);
            }
        }
        return res;
    }
};


void solve(long long N){
    Sieve sieve(pow(2*N, 0.5)+2);
    auto list = sieve.getPrimeFactorList(2*N);
    vector<ll> factors(list.size());
    rep(i,0,list.size()) {
        ll factor = 1;
        rep(j,0,list[i].second) factor *= list[i].first;
        factors[i] = factor;
    }
    ll answer = LLONG_MAX;
    rep(i,0,1 << factors.size()) {
        ll a = 1;
        rep(j,0,factors.size()) {
            if (i & (1<<j)) {
                a *= factors[j];
            }
        }
        ll b = 2*N / a;
        auto res = atcoder::crt({0, -1}, {a, b});
        if (res == pair<ll, ll>(0, 0)) continue;
        ll k = res.first;
        if (k == 0) k = res.second;
        answer = min(k, answer);
    }
    cout << answer << endl;
    return;
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 384876