//include
//------------------------------------------
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>

#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <ctime>

// namespace
using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

// constant
static const ll MOD = 998244353LL;
static const double PI = 3.14159265358979323846;

// conversion
inline ll toint(string s) { ll v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

// print
#define RET(x) return cout << x << endl, 0;

// for loop
#define REP(i, a, b) for ((i) = (ll)(a);(i) < (ll)(b);(i)++)
#define REPD(i, a, b) for (ll i = (ll)(a);(i) < (ll)(b);(i)++)
#define REPI(v, vs) for (auto& v : vs)

//debug
#ifdef LOCAL_ENV
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define DUMP(x)
#define DEBUG(x)
#endif

#define MAX_VALUE 9223372036854775807LL

template <ull N, class T, class... Args, std::enable_if_t<N == 0, int> = 0>
auto make_multiple_vector(Args... args) {
    return T(args...);
}

template <ull N, class T, class... Args, std::enable_if_t<N != 0, int> = 0>
auto make_multiple_vector(ull size, Args... args) {
    using value_type = std::decay_t<decltype(make_multiple_vector<N - 1, T>(args...))>;
    return vector<value_type>(size, make_multiple_vector<N - 1, T>(args...));
}

template<class Integer>
inline Integer get_power(Integer base, ull exponential)
{
	Integer result = 1;
	while (exponential >= 1)
	{
		if (exponential & 1)
		{
			result = result * base;
		}
		base = base * base;
		exponential >>= 1;
	}

	return result;
}

// computational complexity: o(log(max(a, b))) 
inline pair<ll, ll> getBezoutsIdentitySolution(ll a, ll b)
{
	if (b == 0)
	{
		return { 1, 0 };
	}
	auto sol = getBezoutsIdentitySolution(b, a % b);
	return { sol.second, sol.first - (a / b) * sol.second };
}

int solve() {
	ll n;
	cin >> n;
	n *= 2LL;

	ll sqrtn = 1;
	REPD(i, 1, n) {
		if (i * i > n) break;
		sqrtn = i;
	}
	map<ll, ll> factors;
	vector<bool> is_primes(sqrtn + 1LL, true);
	ll quot = n;
	REPD(p, 2, sqrtn + 1) {
		if (!is_primes[p]) continue;
		while (quot % p == 0LL) {
			quot /= p;
			if (factors.count(p) == 0) factors[p] = 0;
			++factors[p];
		}
		for (ll i = 2; i * p <= sqrtn; ++i) {
			is_primes[i * p] = false;
		}
	}
	if (quot != 1LL) factors[quot] = 1;

	ll res = MAX_VALUE;
	ll prime_count = factors.size();
	REPD(bit, 0, 1LL << prime_count) {
		ull target = 0;
		ll a = 1, b = 1;
		for (auto iter = factors.begin(); iter != factors.end(); ++iter) {
			if ((bit >> target) % 2LL == 1LL) a *= get_power(iter->first, iter->second);
			else b *= get_power(iter->first, iter->second);
			++target;
		}
		ll x, y;
		tie(y, x) = getBezoutsIdentitySolution(b, -a);
		if (b * y - a * x == -1LL) x *= -1LL;
		if (x < 0) {
			x += ((-x) / b + 1LL) * b;
		}
		x %= b;
		if (x == 0) x = b;
		res = min(res, a * x);
	}

	cout << res << endl;

	return 0;
}

//main function
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();
	// ll t;
	// cin >> t;
	// REPD(i, 0, t) solve();

	return 0;
}


Measured memory_bytes: 8648