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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll euc(ll a, ll b, ll &x, ll &y) {
  ll xx = y = 0; ll yy = x = 1;
  while (b) {
    ll q = a / b; ll t = b; b = a % b;
    a = t; t = xx; xx = x - q * xx; x = t;
    t = yy; yy = y - q * yy; y = t;
  }
  return a;
}

ll ans, a = 2, n, l, i, j;

void upd(ll x, ll y) {
  if (euc(a*x,y,i,j) > 1) return;
  if ((i = (i % y + y) % y) > 0)
    ans = min({ans, i * x * a - 1, (y-i) * x * a});
}

int main() {
  cin >> n; ans = n + (n % 2 == 0);
  while (n % 2 == 0)
    a *= 2, n /= 2;
  for (ll d = 1; d * d <= n; d++)
    if (n % d == 0)
      upd(d, n / d), upd(n / d, d);
  cout << ans << "\n";
}