Given is an integer N. Find the minimum possible positive integer k such that (1+2+\cdots+k) is a multiple of N. It can be proved that such a positive integer k always exists.

Constraints

* 1 \leq N \leq 10^{15}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N


Output

Print the answer in a line.

Examples

Input

11


Output

10


Input

20200920


Output

1100144
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <cstring>
#include <iomanip>
using namespace std;

#define int long long
#define double long double
#define mp make_pair
#define debug(x) cerr << #x << ": " << x << '\n';
#define fi first
#define se second
#define pb push_back
//typedef long long ll;
typedef pair<int, int> pii;
 
void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}

const int N = 2e5 + 10;
int p[N], pp[N];

void gcd(int a, int b, int &x, int &y) {
	if (a == 0) {
		x = 0; y = 1;
	} else {
		int x2, y2;
		gcd(b % a, a, x2, y2);
		x = y2 - (b / a) * x2;
		y = x2;
	}
}

signed main() {
	fast();
	int n;
	cin >> n;
	int m = 0;
	n *= 2;
	int ans = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i != 0) continue;
		p[m] = i; pp[m] = 1;
		while (n % i == 0) {
			n /= i;
			pp[m] *= i;
		}
		m++;
	}
	if (n > 1) {
		p[m] = pp[m] = n;
		m++;
	}
	int pw = (1 << m);
	for (int msk = 0; msk < pw; msk++) {
		int t = msk;
		int a = 1, b = 1;
		for (int j = 0; j < m; j++, t /= 2) {
			if (t & 1) a *= pp[j];
			else b *= pp[j];
		}
		int x, y;
		gcd(a, b, x, y);
		//debug(a * b << ' ' << x << ' ' << y)
		int k = y * b - 1;
		k %= a * b;
		while (k <= 0) k += a * b;
		if (k == 4742) {
			//cout << a << ' ' << b << '\n';
		}
		if (k < ans) ans = k;
	}
	cout << ans << '\n';
	return 0;
}