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;
#define SZ(a) ((int)(a).size())
typedef long long int64;
int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int64 d = exgcd(b, a % b, x, y);
  int64 t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
int main() {
#ifdef LOCAL
  freopen(".a.in", "r", stdin);
#endif
  ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
  int64 n, res = -1;
  cin >> n;
  if(n==1){
    cout<<1;return 0;
  }
  n *= 2;
  for (int64 i = 1; i * i <= n; ++i)
    if (n % i == 0) {
      int64 x, y, d;
      d = exgcd(i, n / i, x, y);
      if (d == 1 && x != 0 && y != 0) {
        int64 ans = min(abs(i * x), abs(n / i * y));
        res = res == -1 ? ans : min(ans, res);
      }
    }
  cout << res;
  return 0;
}
//2020.09.20 21:59:15
