#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
ll naive(ll n){
    ll sum = 0;
    for(ll k = 1; k <= 100000000; k++){
        sum += k;
        if(sum % n == 0)return k;
    }
    return -1;
}
ll calc(ll n){
    ll cnt = 0;
    while(n % 2 == 0)n /= 2, cnt++;
    return cnt;
}
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

// bit op
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(ull x) { return __builtin_popcountll(x); }
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(ull x) { return __builtin_ctzll(x); }

//binary gcd
ll gcd(ll _a, ll _b) {
    ull a = abs(_a), b = abs(_b);
    if (a == 0) return b;
    if (b == 0) return a;
    int shift = bsf(a|b);
    a >>= bsf(a);
    do {
        b >>= bsf(b);
        if (a > b) swap(a, b);
        b -= a;
    } while (b);
    return (a << shift);
}

template<class T, class U>
T pow_mod(T x, U n, T md) {
    T r = 1 % md;
    x %= md;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

bool is_prime(ll n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1;
    while (d % 2 == 0) d /= 2;
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n <= a) break;
        ll t = d;
        ll y = pow_mod<__int128_t>(a, t, n);  // over
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = __int128_t(y) * y % n;  // flow
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}

ll pollard_single(ll n) {
    auto f = [&](ll x) { return (__int128_t(x) * x + 1) % n; };
    if (is_prime(n)) return n;
    if (n % 2 == 0) return 2;
    ll st = 0;
    while (true) {
        st++;
        ll x = st, y = f(x);
        while (true) {
            ll p = gcd((y - x + n), n);
            if (p == 0 || p == n) break;
            if (p != 1) return p;
            x = f(x);
            y = f(f(y));
        }
    }
}

V<ll> pollard(ll n) {
    if (n == 1) return {};
    ll x = pollard_single(n);
    if (x == n) return {x};
    V<ll> le = pollard(x);
    V<ll> ri = pollard(n / x);
    le.insert(le.end(), ri.begin(), ri.end());
    return le;
}
template <typename T>
void extgcd(T a, T b, T& x, T& y)
{
    if(b != 0){
        extgcd(b,a%b,y,x);
        y -= (a/b)*x;
    }else{
        x = 1;
        y = 0;
    }
}
ll solve(ll n){
    auto d = pollard(n);
    sort(d.begin(), d.end());
    map<ll, int> mp;
    for(auto x: d)mp[x]++;
    vector<pair<ll,int>> a;
    for(auto x: mp)a.push_back(x);
    vector<ll>b;
    for(auto x: a){
        ll t = 1;
        rep(i,x.second)t *= x.first;
        b.push_back(t);
    }
    ll ans = 1LL<<62;
    for(int i = 0; i < (1<<a.size()); i++){
        ll x = 1;
        ll y = 1;
        rep(j,a.size()){
            if(i>>j&1){
                x *= b[j];
            }else{
                y *= b[j];
            }
        }
        {
            x *= 2;
            if(y == 1){
                ll xx = 1;
                ll yy = x + 1;
                ll k = min(x * xx, y * yy);
                if(k != 0)ans = min(ans, k);
            }else if(gcd(x, y)==1){
                ll xx,yy;
                extgcd(-x,y,xx,yy);
                ll k = min(x * xx, y * yy);
                if(k != 0)ans = min(ans, k);
            }
            x /= 2;
        }
        {
            y *= 2;
            if(x == 1){
                ll xx = y - 1;
                ll yy = 1;
                ll k = min(x * xx, y * yy);
                if(k != 0)ans = min(ans, k);
            }else if(gcd(x, y)==1){
                ll xx,yy;
                extgcd(-x,y,xx,yy);
                ll k = min(x * xx, y * yy);
                if(k != 0)ans = min(ans, k);
            }
        }
        
    }
    return ans;
}
int main(){
    ll n;
    cin >> n;
    cout << solve(n) << endl;
    
}


Measured memory_bytes: 3644