#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class T> int Factor_L(T N, T fac[], int fs[]){
  T i;
  int sz = 0;
  if(N%2==0){
    fac[sz] = 2;
    fs[sz] = 1;
    N /= 2;
    while(N%2==0){
      N /= 2;
      fs[sz]++;
    }
    sz++;
  }
  for(i=3;i*i<=N;i+=2){
    if(N%i==0){
      fac[sz] = i;
      fs[sz] = 1;
      N /= i;
      while(N%i==0){
        N /= i;
        fs[sz]++;
      }
      sz++;
    }
  }
  if(N > 1){
    fac[sz] = N;
    fs[sz] = 1;
    sz++;
  }
  return sz;
}
template<class T, class S> inline T pow_L(T a, S b){
  T res = 1;
  res = 1;
  for(;;){
    if(b&1){
      res *= a;
    }
    b >>= 1;
    if(b==0){
      break;
    }
    a *= a;
  }
  return res;
}
inline double pow_L(double a, double b){
  return pow(a,b);
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
int fs;
int fn[50];
long long f[50];
long long safe_mod(long long x, long long m){
  x %= m;
  if (x < 0){
    x += m;
  }
  return x;
}
pair<long long, long long> inv_gcd(long long a, long long b){
  a = safe_mod(a, b);
  if (a == 0){
    return {b, 0};
  }
  long long s = b;
  long long t = a;
  long long m0 = 0;
  long long m1 = 1;
  while (t){
    long long u = s / t;
    s -= t * u;
    m0 -= m1 * u;
    auto tmp = s;
    s = t;
    t = tmp;
    tmp = m0;
    m0 = m1;
    m1 = tmp;
  }
  if (m0 < 0){
    m0 += b / s;
  }
  return {s, m0};
}
pair<long long, long long> crt(const vector<long long>& r, const vector<long long>& m){
  assert(r.size() == m.size());
  int n = int(r.size());
  long long r0 = 0;
  long long m0 = 1;
  for (int i = 0; i < n; i++){
    assert(1 <= m[i]);
    long long r1 = safe_mod(r[i], m[i]);
    long long m1 = m[i];
    if (m0 < m1){
      std::swap(r0, r1);
      std::swap(m0, m1);
    }
    if (m0 % m1 == 0){
      if (r0 % m1 != r1){
        return {0, 0};
      }
      continue;
    }
    long long g;
    long long im;
    std::tie(g, im) = inv_gcd(m0, m1);
    long long u1 = (m1 / g);
    if ((r1 - r0) % g){
      return {0, 0};
    }
    long long x = (r1 - r0) / g % u1 * im % u1;
    r0 += x * m0;
    m0 *= u1;
    if (r0 < 0){
      r0 += m0;
    }
  }
  return {r0, m0};
}
int main(){
  int mask;
  long long N;
  rd(N);
  long long i;
  long long j;
  long long k;
  long long x;
  long long y;
  long long a;
  long long b;
  long long mx;
  long long res = 4611686016279904256LL;
  vector<long long> r(2);
  vector<long long> m(2);
  N *= 2;
  fs =Factor_L(N, f, fn);
  for(mask=(0);mask<(1<<fs);mask++){
    x = y = 1;
    for(i=(0);i<(fs);i++){
      if(((mask) &(1<<(i)))){
        x*= ((pow_L(f[i],fn[i])));
      }
      else{
        y*= ((pow_L(f[i],fn[i])));
      }
    }
    m[0] = x;
    m[1] = y;
    r[0] = 0;
    r[1] = y-1;
    tie(a, b) = crt(r, m);
    if(a==0){
      a += b;
    }
    chmin(res, a);
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200920-1

// --- original code ---
// int fs, fn[50]; ll f[50];
// 
// long long safe_mod(long long x, long long m) {
//     x %= m;
//     if (x < 0) x += m;
//     return x;
// }
// 
// pair<long long, long long> inv_gcd(long long a, long long b) {
//     a = safe_mod(a, b);
//     if (a == 0) return {b, 0};
// 
//     long long s = b, t = a;
//     long long m0 = 0, m1 = 1;
// 
//     while (t) {
//         long long u = s / t;
//         s -= t * u;
//         m0 -= m1 * u;
// 
//         auto tmp = s;
//         s = t;
//         t = tmp;
//         tmp = m0;
//         m0 = m1;
//         m1 = tmp;
//     }
// 
//     if (m0 < 0) m0 += b / s;
//     return {s, m0};
// }
// 
// pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) {
//     assert(r.size() == m.size());
//     int n = int(r.size());
//     long long r0 = 0, m0 = 1;
//     for (int i = 0; i < n; i++) {
//         assert(1 <= m[i]);
//         long long r1 = safe_mod(r[i], m[i]), m1 = m[i];
//         if (m0 < m1) {
//             std::swap(r0, r1);
//             std::swap(m0, m1);
//         }
//         if (m0 % m1 == 0) {
//             if (r0 % m1 != r1) return {0, 0};
//             continue;
//         }
// 
//         long long g, im;
//         std::tie(g, im) = inv_gcd(m0, m1);
// 
//         long long u1 = (m1 / g);
//         if ((r1 - r0) % g) return {0, 0};
// 
//         long long x = (r1 - r0) / g % u1 * im % u1;
// 
//         r0 += x * m0;
//         m0 *= u1;
//         if (r0 < 0) r0 += m0;
//     }
//     return {r0, m0};
// }
// 
// {
//   ll @N, i, j, k, x, y, a, b, mx, res = ll_inf;
//   vector<ll> r(2), m(2);
//   N *= 2;
//   fs = Factor(N, f, fn);
// 
//   rep(mask, 1<<fs){
//     x = y = 1;
//     rep(i,fs) if[BIT_ith(mask,i), x, y] *= (f[i] ** fn[i]);
//     m[0] = x; m[1] = y;
//     r[0] = 0; r[1] = y-1;
//     tie(a, b) = crt(r, m);
//     if(a==0) a += b;
//     res <?= a;
//   }
// 
//   wt(res);
// }


Measured memory_bytes: 3644