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 <climits>
#include <iostream>

using namespace std;
using ll = int64_t;

ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

int main() {
  ll n;
  cin >> n;
  n <<= 1;
  ll ans = n - 1;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i != 0)
      continue;
    ll rem = n / i;
    ll x, y;
    ll g = extgcd(i, rem, x, y);
    if (g != 1)
      continue;
    ll t = x / rem;
    x %= rem;
    y += t * i;
    ans = min(ans, min(abs(x) * i, abs(y) * rem));
    if (x > 0)
      x -= rem, y += t;
    else
      x += rem, y -= t;
    ans = min(ans, min(abs(x) * i, abs(y) * rem));
  }
  cout << ans;
}