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;

#define int long long

//ax+by=1を満たす(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;
}
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}
const long long LINF=1e18;

signed main(){
  /*
  for(int i=2;i<=10;i++)
    for(int j=2;j<=10;j++)
      if(__gcd(i,j)==1)cout<<i<<" "<<j<<" "<<F(i,j)<<endl;
  return 0;
  */
  int n;cin>>n;n*=2;
  vector<int> v;
  for(int i=2;i*i<=n;i++){
    if(n%i)continue;
    int cnt=1;
    while(n%i==0){
      n/=i;
      cnt*=i;
    }
    v.push_back(cnt);
  }
  if(n>1)v.push_back(n);
  int S=v.size();
  int ans=LINF;
  //for(int p:v)cout<<p<<" ";cout<<endl;
  for(int bit=0;bit<(1<<S);bit++){
    int one=1,two=1;
    for(int i=0;i<S;i++){
      if((bit>>i)&1)one*=v[i];
      else two*=v[i];
    }
    if(one==1){
      chmin(ans,two);
      continue;
    }
    if(two==1){
      chmin(ans,one-1);
      continue;
    }
    int x,y;
    extGCD(one,two,x,y);
    //cout<<one<<" "<<two<<" "<<x<<" "<<y<<endl;
    if(x<=0)x=two-x;
    //cout<<one*x-1<<endl;
    chmin(ans,one*x-1);
  }
  cout<<ans<<endl;
}
