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;
using ll = long long;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin >> n;
  vector<ll> fac;
  n *= 2ll;
  ll m = n;
  for(ll i = 2; i*i <= m; ++i){
    if(m%i == 0){
      ll fi = 1;
      while(m%i == 0){
        m /= i;
        fi *= i;
      }
      fac.push_back(fi);
    }
  }
  if(m > 1) fac.push_back(m);
  ll d = fac.size();
  ll ans = n-1;
  for(ll di = (1<<d)-2; di > 0; --di){
    ll t1 = 1;
    for(ll i = 0; i < d; ++i){
      if(di&(1ll<<i)) t1 *= fac[i];
    }
    ll t2 = n/t1;
    if(t2 > t1) continue;
    for(ll i = t1; i <= ans+1; i += t1){
      if((i-1)%t2 == 0){
        ans = min(ans,i-1);
        break;
      }
      if((i+1)%t2 == 0){
        ans = min(ans,i);
        break;
      }
    }
  }
  cout << ans;
  return 0;
}