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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
int main(){
    ll m;
    cin >> m;
  m *= 2;
    ll copy = m;
    map<ll,ll> odd;
    ll even = 1;
    for(int i = 2;i <= sqrt(copy);i++){
        while(m % i == 0){
            if(i == 2)even *= 2;
            else odd[i]++;
            m /= i;
        }
    }
    if(m > 1)odd[m]++;
    ll k = odd.size();
    ll res = pow(10,18);
    for(int i = 0; i < (1<<k); i++){
      ll a = even;
      ll b = 1;
      ll it = 0;
      for(auto item:odd){
          if(i & (1<<it))a *= pow(item.first,item.second);
          else b *= pow(item.first,item.second);
          it++;
      }
      ll x,y;
      extGCD(a,-1*b,x,y);
      if(a * x > 1)res = min(res,a * x);
      extGCD(b,-1*a,x,y);
      if(b * x > 1)res = min(res,b * x);
    }
    if(res == pow(10,18))res = copy;
    else res++;
    cout << res - 1 << endl;
}
