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>
#define ll long long
using namespace std;

ll ans;
ll n,m;
ll p,q,r;

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;
}


//ap+1=bq -> bq-ap=-1

int main(){
  ll x;
  cin>>x;
  if(x==1){
    cout<<1<<endl;
    return 0;
  }
  n=x;
  x*=2;
  m=x;
  map<ll,int> ma;
  vector<ll> vec;
  int t=0;
  if(x%2==0){
    t++;
    vec.push_back(2);
    while(x%2==0){
      ma[2]++;
      x/=2;
    }
  }
  for(ll i=3;i*i<=x;i+=2){
    if(x%i==0){
      t++;
      vec.push_back(i);
      while(x%i==0){
        ma[i]++;
        x/=i;
      }
    }
  }
  if(x!=1){
    vec.push_back(x);
    t++;
    ma[x]++;
  }
  for(int i=0;i<t;i++){
    //cout<<vec[i]<<" "<<ma[vec[i]]<<endl;
  }
  int bitb[t];
  ans=2*n;
  for(int bit=0;bit<(1<<t);bit++){
    for(int i=0;i<t;i++){
      if(bit&(1<<i)){
        bitb[i]=1;
      }
      else{
        bitb[i]=0;
      }
    }
    ll u=1;
    for(int i=0;i<t;i++){
      if(bitb[i]==1){
        u*=pow(vec[i],ma[vec[i]]);
      }
    }
    //cout<<u<<" "<<m/u<<" ";
    extGCD(-u,m/u,p,q);
    //cout<<p<<" "<<q<<endl;
    if(p*q==0){
      continue;
    }
    r=u*p;
    if(r>0){
      ans=min(ans,r);
    }
  }
  cout<<ans<<endl;
}