#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 
using namespace std;

#define int           long long 
#define S             second
#define F             first
#define pb            push_back
#define all(c)        (c).begin(),(c).end()
#define rall(c)       (c).rbegin(),(c).rend() 
#define lb            lower_bound
#define ub            upper_bound
#define si(c)         (int)((c).size())
#define lcm(a, b)      (a * (b / __gcd(a,b)))  
#define inf           (int)(4e18)
#define endl          '\n'
#define mp            make_pair
#define time(s)       (double(clock()-s)/double(CLOCKS_PER_SEC))
#define debug(args...)    _F(#args, args)
#define vi            std::vector<int>
#define pii           pair<int, int> 
#define vpi           vector<pii>
#define ordered_set   tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template<typename T> void _F(const char *name, T arg1){ cerr << name << " = " << arg1 << endl;}
template<typename T, typename... Args> void _F(const char *names, T arg1, Args... args)
{ const char *name = strchr(names, ',');cerr.write(names, name-names) << " = " << arg1 << endl;_F(name+2, args...);}

template< typename T1, typename T2 > istream& operator>>(istream& in, pair<T1, T2> &q){ in >> q.F >> q.S; return in;}
template< typename T1, typename T2 > ostream& operator<<(ostream& out, pair<T1, T2> &q){ out << q.F << " " << q.S; return out;}
template< typename T1, typename T2 > pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F+p2.F, p1.S+p2.S};}
template< typename T1, typename T2 > pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F-p2.F, p1.S-p2.S};}
template< typename T1, typename T2 > bool operator<(pair<T1, T2> p1, pair<T1, T2> p2){ return p1 < p2 ;}

template<typename T> void Unique(vector<T> &v) {
    sort(all(v)), v.resize(distance(v.begin(), unique(all(v))));
}

// int Pow(int x, int p, int m) {
// 	int ans = 1;
// 	while(p > 0) {
// 		if(p&1)ans = (ans*x)%m;
// 		x = (x*x)%m;
// 		p >>= 1;
// 	}
// 	return ans;
// }

int Pow(int a, int m) 
{ 
    int m0 = m; 
    int y = 0, x = 1; 
  
    if (m == 1) 
      return 0; 
  
    while (a > 1) 
    { 
        // q is quotient 
        int q = a / m; 
        int t = m; 
  
        // m is remainder now, process same as 
        // Euclid's algo 
        m = a % m, a = t; 
        t = y; 
  
        // Update y and x 
        y = x - q * y; 
        x = t; 
    } 
  
    // Make x positive 
    if (x < 0) 
       x += m0; 
  
    return x; 
} 

void solve() {
	int n; cin >> n;
	if(n == 1) {
		cout << 1 << endl;
		return;
	}
	vi p;
	n *= 2;
	int m = n;
	for(int i = 2; i*i <= m; i++) {
		if(m%i == 0) {
			while(m%i == 0)m /= i;
			p.pb(i);
		}
	}
	if(m > 1)p.pb(m);

	if(si(p) == 1) {
		if(n%2) {
			cout << n-1 << endl;
		}
		else {
			cout << n*2-1 << endl;
		}
		return;
	}
	vpi v;
	int mn = n%2 ? n : n*2-1;
	for(int i = 1; i < (1<<si(p))-1; i++) {
		int m = n;
		int cur1 = 1, cur2 = 1;
		for(int j = 0; j < si(p); j++) {
			if((i>>j)&1) {
				while(m%p[j] == 0)cur1 *= p[j], m /= p[j];
			}

			else {
				while(m%p[j] == 0)cur2 *= p[j], m /= p[j];
			}
		}
		// if(cur2 > 1e9)continue;
		int inv = Pow(cur1, cur2);
		if(n*2/inv >= cur1)
		mn = min(mn, inv*cur1-1);
	}
	cout << mn << endl;
}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);   
    start = clock(); 

   

    int test = 1;
    // cin >> test;
    
    cout << fixed << setprecision(2);
     
    for(int i = 1; i <= test; ++i){
    	solve();
    }

    cerr << time(start);
    return 0;
}


Measured memory_bytes: 3864