// 乗算は専用にmodを取るmulmodなどを使わないと __int128_t では mod_pow あたりで system_test1.txt でオーバーフローして死んでるっぽい。
// 0_small_32.txt などの小さいケースは BFS した方がいいかもしれない（代わりに素数を小さい方からあてがっていく判定法を用いた）

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)


int const inf = 1<<29;
typedef __int128_t ll;

#include <random>

namespace math { namespace integer {

template<class value_type> value_type mod_mul(value_type x, value_type k, value_type m) { if(k == 0) { return 0; } if(k % 2 == 0) { return mod_mul((x+x) % m, k/2, m); } else { return (x + mod_mul(x, k-1, m)) % m; } }
template<class value_type> value_type mod_pow(value_type x, value_type n, value_type mod) { if(n == 0) { return 1; } if(n % 2 == 0) { return mod_pow(mod_mul(x, x, mod) % mod, n / 2, mod); } else { return mod_mul(x, mod_pow(x, n - 1, mod), mod); } }

}}

using namespace math::integer;

namespace math { namespace prime {

namespace detail {

template <class I>
bool check_small_factors(const I& n) {
   static const uint32_t small_factors1[] = {
      3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u };
   static const uint32_t pp1 = 223092870u;

   uint32_t m1 = n % pp1;

   for(unsigned i = 0; i < sizeof(small_factors1) / sizeof(small_factors1[0]); ++i) {
     if(m1 % small_factors1[i] == 0) { return false; }
   }

   static const uint32_t small_factors2[] = { 29u, 31u, 37u, 41u, 43u, 47u };
   static const uint32_t pp2 = 2756205443u;

   m1 = n % pp2;

   for(unsigned i = 0; i < sizeof(small_factors2) / sizeof(small_factors2[0]); ++i) {
     if(m1 % small_factors2[i] == 0) { return false; }
   }

   static const uint32_t small_factors3[] = { 53u, 59u, 61u, 67u, 71u };
   static const uint32_t pp3 = 907383479u;

   m1 = n % pp3;

   for(unsigned i = 0; i < sizeof(small_factors3) / sizeof(small_factors3[0]); ++i) {
     if(m1 % small_factors3[i] == 0) { return false; }
   }

   static const uint32_t small_factors4[] = { 73u, 79u, 83u, 89u, 97u };
   static const uint32_t pp4 = 4132280413u;

   m1 = n % pp4;

   for(unsigned i = 0; i < sizeof(small_factors4) / sizeof(small_factors4[0]); ++i) {
     if(m1 % small_factors4[i] == 0) { return false; }
   }

   static const uint32_t small_factors5[6][4] = {
      { 101u, 103u, 107u, 109u },
      { 113u, 127u, 131u, 137u },
      { 139u, 149u, 151u, 157u },
      { 163u, 167u, 173u, 179u },
      { 181u, 191u, 193u, 197u },
      { 199u, 211u, 223u, 227u }
   };
   static const uint32_t pp5[6] = 
   { 
      121330189u, 
      113u * 127u * 131u * 137u, 
      139u * 149u * 151u * 157u,
      163u * 167u * 173u * 179u,
      181u * 191u * 193u * 197u,
      199u * 211u * 223u * 227u
   };

   for(unsigned k = 0; k < sizeof(pp5) / sizeof(*pp5); ++k) {
     m1 = n % pp5[k];

     for(unsigned i = 0; i < 4; ++i) {
       if(m1 % small_factors5[k][i] == 0) { return false; }
     }
   }
   return true;
}

inline bool is_small_prime(unsigned n) {
   static const unsigned char p[] = {
      3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u, 
      37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u, 
      79u, 83u, 89u, 97u, 101u, 103u, 107u, 109u, 113u, 
      127u, 131u, 137u, 139u, 149u, 151u, 157u, 163u, 
      167u, 173u, 179u, 181u, 191u, 193u, 197u, 199u, 
      211u, 223u, 227u
   };
   for(unsigned i = 0; i < sizeof(p) / sizeof(*p); ++i) {
      if(n == p[i]) { return true; }
   }
   return false;
}

template<class I> bool cast_to_unsigned(I n) { return static_cast<unsigned>(n % std::numeric_limits<unsigned>::max()); }

} // namespace detail

template<class I, class Engine>
bool miller_rabin_test(const I& n, unsigned trials, Engine& gen) {

  typedef I number_type;

  if((n % 2) == 0) { return false; }
  if(n <= 227) {
    return detail::is_small_prime(detail::cast_to_unsigned(n));
  }

  if(!detail::check_small_factors(n)) { return false; }

  number_type nm1 = n - 1;

  // Fermat test
  number_type q(228), x, y;
  x = mod_pow(q, nm1, n);
  if(x != 1u) { return false; }

  q = n - 1;
  while(!(q & 1)) q >>= 1;

  std::uniform_int_distribution<number_type> dist(1, n - 2);
  
  // Execute miller-rabin-test trials:
  for(unsigned i = 0; i < trials; ++i) {
    x = mod_mul(dist(gen), dist(gen), n - 2) + 1;
    number_type t = q;
    y = mod_pow(x, t, n);
    while(t != n-1 && y != 1 && y != n-1) {
      y = mod_mul(y, y, n);
      t <<= 1;
    }
    if(y != n-1 && (t & 1) == 0) {
      return false;
    }
  }

  return true; // probably prime

}

template<class I>
bool suspect(const I& a, I s, I d, I n) {
  ll x = mod_pow(a, d, n);
  if (x == 1) return true;
  for(int r = 0; r < s; ++r) {
    if(x == n - 1) return true;
    x = mod_mul(x, x, n);
  }
  return false;
}

bool miller_rabin_test2(ll n) {
  if(n <= 1 || (n > 2 && n % 2 == 0)) { return false; }
  vector<int> test = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, -1 };
  ll d = n - 1, s = 0;
  while(d % 2 == 0) { s ++; d /= 2; }
  for(int i = 0; test[i] < n && test[i] != -1; i++) {
    if(!suspect((ll)test[i], s, d, n)) { return false; }
  }
  return true;
}


template<class I>
bool miller_rabin_test(const I& n, int type = 0) {
  if(type == 0) {
    return miller_rabin_test2(n);
  }
  else {
    static std::mt19937 gen;
    return miller_rabin_test(n, 25, gen);
  }
}

}}

map<ll, int> mp = {
  {4,3}, 
  {6,5}, 
  {8,7}, 
  {9,7}, 
  {10,7}, 
  {12,11}, 
  {14,13}, 
  {15,7}, 
  {16,7}, 
  {18,8}, 
  {20,19}, 
  {21,19}, 
  {22,7}, 
  {24,23}, 
  {25,23},
};

int main() {

  string s; cin >> s;
  ll N = 0;
  rep(i, s.size()) {
    N = N * 10;
    N = N + (s[i] - '0');
  }

  if(mp.find(N) != mp.end()) {
    cout << mp[N] << endl;
    exit(0);
  }

  if((N % 8 == 1) && math::prime::miller_rabin_test(N - 8)) {
    cout << 14 << endl;
  }
  else {
    cout << 8 << endl;
  }

  return 0;
}