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 ll long long

int main(){
  ll n;
  cin >> n;
  if(n==1){
    cout << 1 << endl;
    return 0;
  }
  ll i,j;
  vector<ll> p(100,1);
  
  ll m=n*2;
  i=2;
  j=0;
  while(m>=i*i){
    if(m%i==0){
      p.at(j)=i;
      m=m/i;
      j++;
    }else{
      i++;
    }
  }
  p.at(j)=m;
  
  vector<ll> q(20,1);
  ll s=0;
  for(i=0;i<=j;i++){
    if(i==0||p.at(i)==p.at(i-1)){
      q.at(s) *= p.at(i);
    }else{
      s++;
      q.at(s) *= p.at(i);
    }
  }
  
  s++;
  ll mink=2*n-1,h,a,b,k;
  for(i=0;i<(1<<s);i++){
    bitset<50> bi(i);
    a=1;
    b=1;
    for(h=0;h<s;h++){
      if(bi.test(h)){
        a *= q.at(h);
      }else{
        b *= q.at(h);
      }
    }
    if(a>b){
      k=a;
      while(k<mink&&(k+1)%b!=0){
        k += a;
      }
      if(k<mink){
        mink=k;
      }
    }else{
      k=b-1;
      while(k<mink&&k%a!=0){
        k += b;
      }
      if(k<mink){
        mink=k;
      }
    }
  }
  
  cout << mink << endl;
}