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<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline long IN(void)
{
  long x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void OUT(long a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
//https://atcoder.jp/contests/acl1/submissions/16917558
static inline long GCD(long a,long b){return !b?a:GCD(b,a%b);}
//static inline long LCM(long a,long b){return a*b/GCD(a,b);}
static inline long Min(long a,long b){return a<b?a:b;}
static inline long Euclid(long a,long b,long &x,long &y)
{
  if(!b){x=1,y=0;return a;}long ret=Euclid(b,a%b,x,y),t=x;x=y,y=t-(a/b)*y;return ret;
}
static inline long Calc(long i,long j,long ref){long a,b;Euclid(i,j,b,a);b=(b%j+j)%j;return Min(ref,i*b-1);}
int main(void)
{
  long N=IN(),A=N-1;if(N==1){return puts("1"),0;}N*=2;
  for(long i=2;i*i<=N;i++)
  {
    if(N%i){continue;}if(GCD(i,N/i)>1){continue;}A=Calc(i,N/i,A);A=Calc(N/i,i,A);
  }
  return OUT(A),0;
}