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>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

int n, a, b;
int ans;

int gcd(int a, int b) {
  return !b ? a : gcd(b, a%b);
}

pii extgcd(int a, int b) {
  if (!b) return pii(1, 0);
  pii t = extgcd(b, a%b);
  return pii(t.ss, t.ff - t.ss * (a / b));
}

signed main() {
  cin >> n;
  n *= 2;
  ans = n - 1;
  for (int i = 2; i*i <= n; i++) {
    if (n % i == 0 && gcd(i, n/i) == 1) {
      pii t = extgcd(i, n/i);
      if (t.ff < 0) t.ff = -t.ff;
      if (t.ss < 0) t.ss = -t.ss;
      //cout << i << " * " << t.ff << "  " << n/i << " * " << t.ss << "\n";
      //cout << min(t.ff * i, t.ss * (n/i)) << "\n";
      ans = min(ans, min(t.ff * i, t.ss * (n/i)));
    }
  }
  cout << ans << "\n";
}
