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 Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

template<typename T>
T extgcd(T a,T b,T& x,T& y){
  T d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}

template<typename T>
map<T, Int> factorize(T x){
  map<T, Int> res;
  for(Int i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1) res[x]++;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;
  if(n==1) drop(1);

  n*=2;
  auto mp=factorize(n);

  Int m=mp.size();
  // cout<<m<<endl;
  vector<Int> vs;
  for(auto[p,e]:mp){
    vs.emplace_back(1);
    for(Int i=0;i<e;i++) vs.back()*=p;
  }

  Int ans=1e18;
  Int s=1<<m;
  for(Int bit=0;bit<s;bit++){
    Int a=1,b=1;
    for(Int i=0;i<m;i++){
      if((bit>>i)&1) a*=vs[i];
      else b*=vs[i];
    }
    Int x,y;
    extgcd(a,b,x,y);
    x-=b;y-=a;
    for(Int k=0;k<5;k++){
      // if(0<x and y<0) cout<<a<<' '<<b<<' '<<x<<' '<<y<<":"<<a*x<<' '<<b*-y<<newl;
      if(0<x and y<0) chmin(ans,b*-y);
      x+=b;y+=a;
    }
  }
  cout<<ans<<newl;
  return 0;
}
