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 rep(i,n) for(long long i=0;i<n;++i)

long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        long long d = extend_gcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}

int main(){
  long long n;
  scanf("%lld",&n);
  if(n==1<<0 or n==1<<1 or n==1<<2 or n==1<<3
     or n==1<<4 or n==1<<5 or n==1<<6 or n==1<<7
     or n==1<<8 or n==1<<9 or n==1<<10 or n==1<<11
     or n==1<<12 or n==1<<13 or n==1<<14 or n==1<<15
     or n==1<<16 or n==1<<17 or n==1<<18 or n==1<<19
     or n==1<<20 or n==1<<21 or n==1<<22){
    cout << n*2-1 << endl;
    return 0;
  }
  
  vector<long long> primes;
  for(long long i=2;i*i<=n;++i){
    if(n%i==0){
      long long tmp=1;
      while(n%i==0){
        tmp*=i;
        n/=i;
      }
      primes.push_back(tmp);
    }
  }
  if(n!=1){
    primes.push_back(n);
  }
  
  if(primes[0]%2==0){
    primes[0]*=2;
  }
  else{
    primes.push_back(2);
  }
  
  long long ans=1e16;
  for(long long i=0;i<(1<<primes.size());++i){
    long long a=1;
    long long b=1;
    for(int j=0;j<primes.size();++j){
      if(i&(1<<j)){
        a*=primes[j];
      }
      else{
        b*=primes[j];
      }
    }
    if(a==1 or b==1){
      continue;
    }
    long long x=1;
    long long y=1;
    extend_gcd(a,b,x,y);
    long long k=min(a*abs(x),b*abs(y));
    if(k==0){
      continue;
    }
    ans=min(ans,k);
  }
  
  cout << ans << endl;
  
  return 0;
}