#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <fstream>
#include <iterator>
#include <random>
#include <chrono>


#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

using namespace std;

ll modd = 1000 * 1000 * 1000 + 7;

ll gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0, ll &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

int main()   {

      ios_base::sync_with_stdio(false);

      cout.precision(17);
      mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no

//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readll(n);

/*        forr(i,1,2*n) {
            if ((i*(i+1))/2 % n==0)  {
                cout << i << endl; break;
            }
        } */

        ll ret = 2*n;
        for(ll d = 1; d*d<=n; ++d) {
            if (n%d!=0) {continue;}
            ll d1 = d, d2 = n/d, alpha1, alpha2, gg;
            bool rr = find_any_solution(d2, -d1, 1, alpha2, alpha1, gg);
            if (!rr) {continue;}
            if (alpha1<=0) {
                ll kk = abs(alpha1)/d2+1;
                alpha1 += d2 * kk;
                alpha2 += d1 * kk;
            }
            ll kk = alpha1/d2;
            alpha1 -= d2 * kk;
            alpha2 -= d1 * kk;
            if (alpha1==0) {
                alpha1 += d2; alpha2 += d1;
            }
            if ((alpha1 % 2==0) || (alpha2 % 2==0)) {                
              ret = min(alpha1*d1, ret);
            } else {
                if ((d1%2==0) && (d2%2==0)) {
                    continue;
                }
                alpha1 += d2;
                alpha2 += d1;
                ret = min(alpha1*d1, ret);
            }
            d2 = d, d1 = n/d;
            rr = find_any_solution(d2, -d1, 1, alpha2, alpha1, gg);
            if (!rr) {continue;}
            if (alpha1<=0) {
                ll kk = abs(alpha1)/d2+1;
                alpha1 += d2 * kk;
                alpha2 += d1 * kk;
            }
            kk = alpha1/d2;
            alpha1 -= d2 * kk;
            alpha2 -= d1 * kk;
            if (alpha1==0) {
                alpha1 += d2; alpha2 += d1;
            }
            if ((alpha1 % 2==0) || (alpha2 % 2==0)) {                
              ret = min(alpha1*d1, ret);
            } else {
                if ((d1%2==0) && (d2%2==0)) {
                    continue;
                }
                alpha1 += d2;
                alpha2 += d1;
                ret = min(alpha1*d1, ret);
            }
        }
        cout << ret << endl;

    }
    return 0;
}


Measured memory_bytes: 3656