#include <bits/stdc++.h>

#define ll __int128
#define int long long

void extgcd(ll a, ll b, ll& d, ll& x, ll& y) {
    if (!b) d = a, x = 1, y = 0;
    else { extgcd(b, a % b, d, y, x); y -= x * (a / b); }
}

ll inv(ll a, ll b) {
    ll d, x, y; extgcd(a, b, d, x, y);
    return d == 1 ? (x + b) % b : 1e18;
}

void write(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}

int n, m;
std::vector<int> a;
ll cx, cy;
ll ans;

void dfs(int x) {
    if (x >= a.size()) {
        //if (cx < cy) return;
        if (cx == 1 || cy == 1) return;
            ll cur = inv(cy, cx) * cy - 1;
           // write(cx), putchar(' '), write(cy), putchar(' '), write(cur), putchar('\n');
            ans = std::min(ans, cur);
        
        return;
    }
    cx = cx * a[x]; dfs(x + 1); cx = cx / a[x];
    cy = cy * a[x]; dfs(x + 1); cy = cy / a[x];
}

bool prime(ll t) {
    if (t < 2) return 0;
    for (ll i = 2; i * i <= t; ++i)
        if (t % i == 0) return 0;
    return 1;
}

/*namespace pollard {
    using namespace std;
#define LL long long

LL Prime[11] = {2, 3, 5, 7, 13, 17, 19, 23} ;

inline LL expow(LL a, LL b, LL p){
    LL res = 1 ;
    while (b){
        if (b & 1) 
            (res *= a) %= p ;
        (a *= a) %= p, b >>= 1 ; 
    }
    return res % p ;
}
inline bool Test(LL p, LL x){
    LL r = 0, d = x - 1 ;
    while (!(d & 1)) d >>= 1, ++ r ;
    for (LL i = expow(p, d, x), j ; r ; -- r){
        j = i * i % x ;
        if (j == 1){
            if (i == 1 || i == x - 1) 
                return 1 ; 
            return 0 ;
        }
        i = j ;
    }
    return 0 ;
}
inline bool Miller_Rabin(LL x){
    if (x == 1) return 0 ;
    for (int i = 0 ; i < 8 ; ++ i){
        if (x == Prime[i]) return 1 ;
        if (!(x % Prime[i])) return 0 ;
        if (!Test(Prime[i], x)) return 0 ;
    }
    return 1 ;
}
LL res[100], tot ;
LL gcd(LL x, LL y) {
    LL z = 1;
    while (z) z = x % y, x = y, y = z;
    return x;
}
inline int pksrand(){
    return rand() << 15 ^ rand() ;
} // 2
inline LL Irand(LL x){
    return (((LL)pksrand()) << 30 ^ pksrand()) % x ; //2
}
inline LL guisuMul(LL a, LL b, LL x){
    return (a * b - (LL) ((long double) a * b / x + 1e-9) * x) % x;
} 
inline LL qwq(LL x){
    LL A = Irand(x), C = Irand(x) ;
    LL t1 = A, t2 = (guisuMul(A, A, x) + C) % x ; // 1
    LL dif = max(t1, t2) - min(t1, t2), G = gcd(x, dif) ;
    while (G == 1){
        t1 = (guisuMul(t1, t1, x) + C) % x ;
        t2 = (guisuMul(t2, t2, x) + C) % x ;
        t2 = (guisuMul(t2, t2, x) + C) % x ;
        dif = max(t1, t2) - min(t1, t2), G = gcd(x, dif) ;
    }
    return G ;
}
inline void Pollard_Rho(LL x){
    if (x == 1) return ;
    if (Miller_Rabin(x)) {
        res[++ tot] = x ; return ;
    }
    LL y = x ; while (y == x) y = qwq(x) ;
    Pollard_Rho(y), Pollard_Rho(x / y) ;
}
void pr(ll x) {
    tot = 0;
    Pollard_Rho(x);
    std::sort(res + 1, res + tot + 1);
    int cur = res[1];
    for (int i = 2; i <= tot; ++i) {
        if (res[i] == res[i - 1]) cur *= res[i];
        else {
            a.push_back(cur);
            cur = 1;
        }
    }
    if (cur > 1) a.push_back(cur);
}
}*/

signed main() {
    std::cin >> n;
    if (n == 1) { puts("1"); return 0; }
    if (n == 2) { puts("3"); return 0; }
    n *= 2;
    int t = n, j = 2;
    while (t > 1) {
        if (j % (ll)(1e7) == 0)
            if (prime(t)) { a.push_back(t); break; }
        int tmp = 1;
        while (t % j == 0 && t > 1) t /= j, tmp *= j;
        if (tmp > 1) a.push_back(tmp);
        ++j;
        //if (j % 10000 == 0) write(j), putchar(' '), write(t), putchar('\n');
    }
    //pollard::pr(n);
    //puts("OK");
    cx = cy = 1;
    ans = n - 1;
    dfs(0);
    write(ans);
    putchar('\n');
    return 0;
}

Measured memory_bytes: 3636