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>
using namespace std;

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

long long n, n2;
long long calc(long long a, long long b);

int main() {
  cin >> n;
  long long res = n;
  n *= 2;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) res = min(res, calc(i, n / i));
  cout << res << endl;
  return 0;
}

long long calc(long long a, long long b) {
  long long x, y, g;
  g = mygcd(a, b, x, y);
  if (g != 1) return n;
  if (x > 0) {
    swap(a, b);
    swap(x, y);
  }
  long long num = -x / b, res = n;
  x %= b;
  y -= a * num;
  if (x == 0) {
    x -= b;
    y += a;
  }
  res = min(res, -a * x * g);
  y -= a;
  x += b;
  if (y == 0) {
    x += b;
    y -= a;
  }
  res = min(res, -b * y * g);
  return res;
}