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 <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

using ll = long long;

std::vector<ll> divisor(ll n) { 
  std::vector<ll> ret;
  for (ll i = 1; (ll)i*i <= n; ++i) { 
    if (n % i == 0) {
      ret.push_back(i);
      if (i*i != n) { ret.push_back(n/i); }
    }
  }
  std::sort(ret.begin(), ret.end());
  return ret;
};

template< typename T >
T extgcd(T a, T b, T &x, T &y) {
  T 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;
  if (n == 1) {
    cout << n << endl;
    return 0;
  }
  ll n2 = 1;
  bool ok = false;
  while (n2 < n) {
    n2 *= 2;
    if (n2 == n) { ok = true; break; }
  }
  if (ok) {
    cout << 2*n-1 << endl;
    return 0;
  }
  vector<ll> divs = divisor(2*n);
  ll ans = 3*n;
  for (ll a: divs) {
    ll b = -2*n/a;
    ll x, y;
    ll sol = extgcd(a, b, x, y);
    if (x == 0 || y == 0) continue;
    if (sol != 1) continue;
    ans = min(ans, a*x-1);
    // cout << sol << " " << a << " " << b << " " << x << " " << y << endl;
  }
  cout << ans << endl;
}

