#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
// const i64 smod = 998'244'353ll;

const i64 inf = mod;

const long double eps = 1e-8;

i64 R;
i64 m;
i64 n;

vector<i64> cmp;
vector<i64> all;

i64 gcd(i64 a, i64 b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

i64 val(i64 i) {
    return i * (i + 1) / 2;
}

i64 brute(i64 n) {
    for (i64 i = 1; i <= 2 * n; i++) {
        if (val(i) % n == 0) {
            return i;
        }
    }

    throw 1;
}

map<i64, i64> get_primes(i64 n) {
    map<i64, i64> ans;

    for (i64 i = 2; i <= sqrt(n) + 2; i++) {
        while (n % i == 0) {
            ans[i] += 1;
            n /= i;
        }
    }

    ans[n] += 1;
    ans.erase(1);
    return ans;
}

void gen(map<i64, i64>& primes, set<pair<i64, i64>>& res) {
    vector<i64> q;
    for (auto e : primes) {
        q.push_back(1);
        for (i64 i = 0; i < e.second; i++) {
            q.back() *= e.first;
        }
    }

    i64 mx = (1ll << q.size());
    for (i64 m = 0; m < mx; m++) {
        i64 u = 1;
        i64 v = 1;

        for (i64 i = 0; i < q.size(); i++) {
            if (m & (1ll << i)) {
                u *= q[i];
            }
            else {
                v *= q[i];
            }
        }

        res.insert({min(u, v), max(u, v)});
    }
}


void check_prime(i64 u, i64 v) {
    for (auto p : all) {
        if (v * p > R) {
            break;
        }

        if ((v * p + 1) % u == 0) {
            R = min(R, v * p);
        }
        if ((v * p - 1) % u == 0) {
            R = min(R, v * p - 1);
        }
    }
}

void check(i64 u, i64 v) {
    for (i64 p = 1; p <= n; p++) {
        if (v * p > R) {
            break;
        }

        //if (gcd(p, u) != 1) {
        //    continue;
        //}

        if ((v * p + 1) % u == 0) {
            R = min(R, v * p);
        }
        if ((v * p - 1) % u == 0) {
            R = min(R, v * p - 1);
        }
    }
}


i64 solve(i64 t) {
    n = t;

    m = sqrt(n) + 2;
    R = 2 * n - 1;

    cmp.resize(m + 1);
    all.push_back(1);
    for (i64 i = 2; i <= m; i++) {
        if (cmp[i]) {
            continue;
        }
        all.push_back(i);
        for (i64 j = 2; i * j <= m; j++) {
            cmp[i * j] = 1;
        }
    }


    auto primes = get_primes(2 * n);

    set<pair<i64, i64>> can;
    gen(primes, can);

    for (auto e : can) {
        check_prime(e.first, e.second);
    }

    for (auto e : can) {
        check(e.first, e.second);
    }

    return R;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed); cerr.precision(15); cerr.setf(ios::fixed);

    cin >> n;

    bool fake = false;
    if (!fake) {
        cout << solve(n) << endl;
    }
    else {
        i64 T = 100;

        static std::default_random_engine rng;
        std::uniform_int_distribution<i64> dist(1, n);

        for (i64 tt = 1; tt <= T; tt++) {
            n = dist(rng);

            i64 sres = solve(n);
            i64 bres = brute(n);

            if (sres != bres) {
                throw 1;
            }
        }
    }





    return 0;
}

Measured memory_bytes: 265904