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 <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
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;
}
int main(){
  long long N;
  cin>>N;
  N*=2;
  long long M=N;
  vector<long long> d;
  for(long long i=2;i*i<=M;i++){
    if(M%i==0){
      long long k=1;
      while(M%i==0){
        M/=i; k*=i;
      }
      d.push_back(k);
    }
  }
  if(M!=1) d.push_back(M);
  long long answer=N;
  long long l=1;
  for(int i=0;i<d.size();i++) l*=2;
  for(long long i=0;i<l;i++){
    long long dev=1;
    long long judge=1;
    for(int j=0;j<d.size();j++){
      if((i%(judge*2))/judge==1) dev*=d[j];
      judge*=2;
    }
    long long x,y;
    extgcd(N/dev,dev,x,y);
    y*=-1;
    if(y>0) y%=(N/dev);
    else{
      y+=(abs(y)/(N/dev)+1)*(N/dev);
    }
    answer=min(answer,y*dev);
  }
  cout<<answer<<endl;
  
  return 0;
}