Example

Input

3


Output

1
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }

ll N;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    cin >> N;
}

ll euler_phi(ll n) {
  ll ret = n;
  for(ll i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret -= ret / i;
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) ret -= ret / n;
  return ret;
}


template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1LL;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}

map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

ll __gcd(ll a,ll b){
    if(a>b) return __gcd(b,a);
    if(a==0LL) return b;
    if(a==1LL) return 1LL;
    return __gcd(b%a,a);
}

ll __lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

ll Carmichael(ll n){
    auto pf = prime_factor(n);
    // if(n==2LL) return n;
    // if(pf.size()==1) {
    //     for(auto p:pf) return (p.first-1LL);
    //     }
    if(pf.size()==1){
      for(auto p:pf){
        if(p.first==2LL){
          if(p.second<=2) return p.second;
          else return pow(2LL,(p.second-2LL));
        }
        else return (p.first-1LL)*pow(p.first,(p.second-1LL));
      }
    }
    ll ret=1LL;
    for(auto p:pf) {
        // if(p.first==2LL) ret = __lcm(ret,2LL);
        // else ret = __lcm(ret,(p.first-1LL));
        ret = __lcm(ret,Carmichael(pow(p.first,p.second)));
        }
    return ret;
}

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int solve(){
    auto pf = prime_factor(N);
    // Nを素因数分解したとき、2乗以上される因子があるとき。
    for(auto p:pf) if(p.second>1) {SAY("Nを素因数分解したとき、2乗以上される因子があるとき。"); cout << "-1" << endl; return -1;}
    // Nが素数の場合
    if(pf.size()==1){SAY("Nが素数の場合") cout << 1 << endl; return 1;}
    // Nが偶数の場合
    if(N%2==0) {SAY("Nが偶数の場合") cout << "-1" << endl; return -1;}
    vector<ll> car;
    auto div = divisor(N);
    DBG(div)
    ll L=Carmichael(N);
    // for(auto p:div) car.push_back(Carmichael(p));
    // // for(auto p:pf) car.push_back(Carmichael(p.first));
    // for(auto p:pf) car.push_back(p.first-1);
    // // car.push_back(Carmichael(N));
    // // car.push_back(__lcm();
    // DBG(car)

    // Nは偶数の場合：で除かれてる。。。はず。 
    // for(auto c:car){
    //     if(N%c==0){cout << "-1" << endl; return 0;}
    // }
    // set<ll> car;
    // for(auto p:pf){
    //     ll c=p.first-1;
    //     car.insert(c);
    //     }
    vector<pll> modpows;
    // for(auto p:pf) modpows.push_back({1LL,(p.first-1LL)});
    map<ll,bool> used;
    for(auto p:div) {
      ll lamd = Carmichael(p);
      if(used[lamd]) continue;
      modpows.push_back({1LL,lamd});
      used[lamd] = true;
      }
    if(!used[L]) modpows.push_back({1LL,L});
    DBG(modpows)
    vector<ll> klcms;
    for(auto la:modpows){
      if(__gcd(N,la.second)==1LL){
        DBG(la.second)
        klcms.push_back(Carmichael(la.second));
      }
    }
    ll KLCM=1LL;
    DBG(klcms)
    for(auto lcm:klcms) KLCM = __lcm(KLCM,lcm);
    ll k=KLCM;
    DBG(KLCM)
    // while(k*k < N)
    // {
    //     bool isOk=true;
    //     for(auto &mps:modpows){
    //         mps.first *= mod_pow(N,k,mps.second);
    //         // mps.first %= mps.second;
    //         if(mps.first!=1LL){
    //             isOk=false;
    //         }
    //     }
    //     DBG(modpows)
    //     // for(auto c:car){
    //     //     if(mod_pow(N%c,k,c)!=1){
    //     //         isOk=false;
    //     //         break;
    //     //     }
    //     // }
    //     if(isOk){cout << k << endl; return k;}
    //     k+=KLCM;
    // }

    for(ll k=1LL; k <= KLCM;k++)
    {
        bool isOk=true;
        for(auto &mps:modpows){
            mps.first *= N%mps.second;
            mps.first %= mps.second;
            if(mps.first!=1LL){
                isOk=false;
            }
        }
        DBG(modpows)
        // for(auto c:car){
        //     if(mod_pow(N%c,k,c)!=1){
        //         isOk=false;
        //         break;
        //     }
        // }
        if(isOk){cout << k << endl; return k;}
    }

    SAY("その他.うまいkが見つからなかった")
    cout << "-1" << endl;
    return -1;
}   

// x^(n^k) mod m
ll mod_pow_induc(ll x, ll n, ll m, ll k){
  if(k==-1LL) return 1LL;
  if(k==0LL) return mod_pow(x,1LL,m);
  if(k==1LL) return mod_pow(x,n,m);
  else return mod_pow_induc(mod_pow(x,n,m),n,m,k-1);
}

void sample(ll N, ll ans){
  // ll po=pow(N,ans)
  // llだと桁が足りない。
  if(ans==-1) return;
    for (ll i = 1; i < min(N/ans,(ll)100); i++)
    {
      // iとNが互いに素
      // ll po;
      // ll m=__gcd(N,i);
      // po = mod_pow(N,ans,Carmichael(N/m));
      // DBG(po)
      // 微妙に違う・・・
      // else po=mod_pow(N,ans,Carmichael(i));
      // cout << mod_pow(i,po,N) << endl;
      cout << mod_pow_induc(i,N,N,ans) << endl;
    }
    
}

int main()
{
    input();
    // N=1234567;
    ll ans = solve();
    // sample(N, ans);
    return 0;
}

