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;
const int N = 1e5+100;
typedef long long ll;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

int ish[N],prime[N],pcnt;

inline void Sieve(){
   pcnt = 0;
   fr(i,2,N-1){
      if(!ish[i])prime[++pcnt] = i;
      for(int j = 1;j <= pcnt && prime[j]*i < N; ++j){
         ish[i*prime[j]] = 1;
         if(i%prime[j] == 0)break;
      }
   }
}
map<ll,int> m1;
ll n;
ll ans;

inline void solve(ll a,ll b){
   if(a < b)swap(a,b);
   for(ll w = a;w <= ans;w += a){
      if((w-1)%b == 0){
         ans = min(ans,w-1); return ;
      }
      if((w+1)%b == 0){
         ans = min(ans,w); return ;
      }
   }
}

ll wn;
inline void check_sqr(){
   ll L = 2,R = (int)1e8;
   while(L < R){
      ll mid = (L+R)/2;
      if(mid*mid == wn){
         wn = 1; m1[mid] += 2; return ;
      } else if(mid*mid < wn)L = mid+1;
      else R = mid;
   }
}

pair<ll,int> p1[21];

int main(){
   Sieve();
   scanf("%lld",&n);
   n *= 2;
   wn = n;
   ans = n-1;
   fr(i,1,pcnt){
      while(wn%prime[i] == 0){
         wn /= prime[i]; ++m1[prime[i]];
      }
   }
   check_sqr();
   if(wn > 1)++m1[wn];

   int sz = m1.size(),cnt = 0;
   for(map<ll,int>::iterator i = m1.begin();i != m1.end(); ++i){
      p1[cnt++] = *i;
   }

   fr(i,0,(1<<sz)-1){
      ll w1,w2;
      w1 = w2 = 1;
      fr(j,0,cnt-1){
         if((i >> j)&1){
            fr(z,1,p1[j].second)w1 *= p1[j].first;
         } else {
            fr(z,1,p1[j].second)w2 *= p1[j].first;
         }
      }
      solve(w1,w2);
   }

   printf("%lld\n",ans);
}
