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<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<string.h>
#include<set>
#include<map>
#define LL long long
#define pr pair<int,int>
#define fr first
#define sc second
//#define mp make_pair
using namespace std;
LL read( ){LL sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) return -sum;return sum;}
void read(int &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
void read(LL &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
const int N=5000005;
const int M=20;
int m,pri[N];bool S[N+1];
int n;LL P[20],ans;
inline void exgcd(LL a,LL b,LL &x,LL &y)
{
  if(!b) {x=1;y=0;return;}
  exgcd(b,a%b,x,y);
  LL t=x;x=y;y=t-a/b*y;
}
void DFS(int p,LL a,LL b)
{
  if(p==n+1)
    {
      LL x,y;
      exgcd(a,b,x,y);y=-y;        
      y%=a;if(y<=0) y+=a;
      ans=min(ans,y*b);
      return;
    }
  DFS(p+1,a*P[p],b);
  DFS(p+1,a,b*P[p]);
}
int main( )
{
  int i,j;
  for(i=2;i<=N;i++)
     {
      if(S[i]) continue;
      pri[++m]=i;
      for(j=i+i;j<=N;j+=i) S[j]=1;
    }
  LL X=read( )*2;
  n=0;ans=X-1;
  for(i=1;i<=m&&pri[i]<=X;i++)
    {
      if(X%pri[i]!=0) continue;
      P[++n]=1;
      while(X%pri[i]==0) X/=pri[i],P[n]*=pri[i];
    }
  if(X>1) P[++n]=X;
  DFS(1,1,1);
  printf("%lld\n",ans);
  return 0;
}

