#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vvvi = vector<vvi>; // intの2次元の型に vvi という別名をつける
const ll llMAX=9223372036854775807LL; 
const ll llMIN=-9223372036854775808LL;

void myprint1D(vi &data)
{
  REP(i,data.size())
    cout<<data[i]<<" ";
  cout<<endl;
}

//配列を[y][x]で表示
void myprint2D_T(vvi &data)
{
  REP(i,data.size())
    myprint1D(data[i]);
}

//配列を[x][y]で表示
void myprint2D(vvi &data)
{
  ll l1=data.size();
  ll l2=data[0].size();
  REP(j,l2){
    REP(i,l1)
      cout<<data[i][j]<<" ";
    cout<<endl;
  }
}

//print(a,b...)って使い方
void print1(ll a){cout<<a<<endl;}
void print2(ll a,ll b){cout<<a<<" "<<b<<endl;}
void print3(ll a,ll b,ll c){cout<<a<<" "<<b<<" "<<c<<endl;}
void print4(ll a,ll b,ll c,ll d){cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;}
void print5(ll a,ll b,ll c,ll d,ll e){cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;}


//mapの使い方
#include <map>

ll n,MOD;

ll gcd(ll a,ll b){
  ll r = a % b;
  while(r!=0LL){
    a = b;
    b = r;
    r = a % b;
  }
return b;
}




//moddivとnCk
ll moddiv(ll a,ll b){
	ll x0=MOD,x1=b,x2,n0=0LL,n1=1LL,n2,t=a%b,m,ans;
	if (t==0LL) return a/b;
		for(int i=0;i<900;i++){
      m=x0/x1;
      x2=x0-x1*m;
      n2=(n0-m*n1)%MOD;
      if (x2==1LL){
        ans=(n2+MOD)%MOD;
        break;
      }
      x0=x1;x1=x2;
      n0=n1;n1=n2;
    }
	return (a+((t*ans)%MOD)*b-t)/b;
}
//剰余の割ざん

//aのn乗 mod c
ll expmod(ll a,ll n){
  ll ans=1LL,aa=a,beki=n;
  for(int i=0;i<64;i++){
    if (beki%2==1LL) ans=ans*aa%MOD;
    aa=aa*aa%MOD;
    beki/=2LL;
    if (beki==0LL)break;
  }
  return ans;
}

//nCk
vi mulmod(500001);//0!,1!,2!,3!,4!,,,,
void first_nCk(){
  mulmod[0]=1LL;
  for(ll i=1;i<500001;i++){
    mulmod[i]=mulmod[i-1]*i%MOD;
  }
}
ll nCk(ll nn,ll kk){
  return moddiv(mulmod[nn],mulmod[kk]*mulmod[nn-kk]%MOD);
}

ll garner(ll a,ll b,ll ar,ll br){
  ll ret=(ar+(br-ar)*moddiv(1,a)%b*a)%(a*b)-1;
  return (ret+a*b)%(a*b);
}




int main(){
  ll ans=0;
  cin >> n;
  if (n==1){cout<<1<<endl;return 0;}

  ans=n-1;

    // エラトステネスのふるい
  ll MAX = 33101000;
  vector<int> is_prime(MAX, 1);
  is_prime[0] = 0, is_prime[1] = 0;
  for (ll i = 2; i < MAX; ++i) {
      if (!is_prime[i]) continue;
      for (ll j = i*2; j < MAX; j += i) is_prime[j] = 0;
  }



map<ll, ll> nums;
for (ll i = 2; i < MAX; ++i) {
  if (is_prime[i]) {
    for(int j=0;j<128;j++)
    {
      if (n%i!=0)break;
      n/=i;
      nums[i]++;
    }
  }
}
nums[2]+=1;
if (n!=1)
nums[n]++;



ll cnt=0;
for (auto it : nums) {
  cnt++;
}
vi soinsu(cnt);
vi nokz(cnt);
cnt=0;
ll zn=1;
for (auto it : nums) {
  soinsu[cnt]=it.first;
  nokz[cnt]=it.second;
  //cout<<it.first<<" "<<it.second<<endl;
  zn*=(it.second+1);
  cnt++;
}





for(int i=0;i<zn;i++)
{
  ll ii=i;
  ll val0=0;
  ll val1=0;
  ll vala0=1;
  ll vala1=1;
  for(int j=0;j<cnt;j++)
  {
    ll ama=ii%(nokz[j]+1);
    ii/=(nokz[j]+1);
    val0+=(nokz[j]-ama)*soinsu[j];
    ll mm=nokz[j]-ama;
    for(int k=0;k<mm;k++)
    {
      vala0*=soinsu[j];
    }
    val1+=(ama)*soinsu[j];
    
    mm=ama;
    for(int k=0;k<mm;k++)
    {
      vala1*=soinsu[j];
    }
  }
  

    //cout<<vala0<<endl;
    //cout<<vala1<<endl;
  if (vala1==1)continue;
  if (vala0==1)continue;
  if (gcd(vala1,vala0)==1){
    ll ar,br,a,b;
    ar=0;
    br=1;
    a=vala1;
    b=vala0;
    MOD=b;
    //ll tmp=ar+(br-ar)*moddiv(1,a)%b*a;
    ans=min(ans,garner(a,b,ar,br));

    //cout<<moddiv(1,a)<<endl;
    a=vala0;
    b=vala1;
    MOD=b;
    ans=min(ans,garner(a,b,ar,br));
    //cout<<a<<" "<<b<<endl;
    //cout<<moddiv(1,a)<<endl;
  }

}







  cout<<ans<<endl;
  return 0;
}





Measured memory_bytes: 136568