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;
typedef pair<long,long>P;
P solve(P p){
  long x=p.first,y=p.second;
  if(x%y==1)return P(1,-(x/y));
  if(y==-1)return P(1,x-1);//x -1  * 1 x-1
  P r_=solve(P(y,x%y));
  long a_=r_.first,b_=r_.second;
  P r(b_,a_-b_*(x/y));
  return r;
}

int main(){
  long N;cin>>N;long n=2*N;
  map<long,long>p;
  for(long i=2;i*i<=n;i++){
    while(n%i==0){
      if(p[i]==0)p[i]=i;
      else p[i]*=i;
      n/=i;
    }
  }
  if(n!=1)p[n]=n;
    
  long ans=1000000000000000;
  vector<long>keys;
  for(auto [key,value]:p)keys.push_back(key);
  for(long i=0;i<(1<<keys.size());i++){
    long x=1,y=1;
    bitset<20>bit(i);
    for(long j=0;j<keys.size();j++){
      if(bit.test(j)) x*=p[keys[j]];
      else y*=p[keys[j]];
    }
    
    
    //if(x!=1&&y!=1)
    P p=solve(P(x,-y));
    long r=max((-p.first+y-1)/y,(-p.second+x-1)/x);
    long b=p.second+x*r;
    if(b*y>0)ans=min(ans,b*y);
    //cout<<b*y<<endl;
  }
  cout<<ans;
}
/*
k+1 k=2Nr


2N=x*y
k+1=ax
k=byとして

1=xa+(-y)b
このようなa,bの一般解を求めたとして, a>0,b>0を満たす最小のa,bを求めればいい

a=a0+yr
b=b0+xr
a>0,b>0となるような最小のrを探す
a0+yr>0 && b0+xr>0
r>-a0/y, -b0/x

2 -1*  =1
2の場合
1 2 3

1の場合1
*/