#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000001;
namespace fancy_dumper {
struct ToggleSeparator {};
template <ostream *Out>
struct DumpFirst {};
template <ostream *Out>
struct Dumper {
  static void *&last() {
    static void *p;
    return p;
  }
  static const char *&separator() {
    static const char *s = " ";
    return s;
  }
  static const char *&separatorNewLine() {
    static const char *s = "\n";
    return s;
  }
  static const char *&unseparator() {
    static const char *s = "=";
    return s;
  }
  Dumper() { last() = this; }
  ~Dumper() {
    if (this == last()) {
      *Out << separatorNewLine();
      last() = 0;
    }
  }
  Dumper operator,(ToggleSeparator) {
    std::swap(separator(), unseparator());
    return Dumper();
  }
};
template <ostream *Out, class T>
Dumper<Out> operator,(Dumper<Out>, const T &e) {
  *Out << Dumper<Out>::separator() << e;
  return Dumper<Out>();
}
template <ostream *Out, class T>
Dumper<Out> operator,(DumpFirst<Out>, const T &e) {
  *Out << e;
  return Dumper<Out>();
}
}  // namespace fancy_dumper
template <class T, class Y>
ostream &operator<<(ostream &o, const pair<T, Y> &p) {
  return o << p.first << ' ' << p.second;
}
template <class T>
ostream &operator<<(ostream &o, const vector<T> &v) {
  bool isBegin = true;
  for (auto &e : v) {
    if (!isBegin) {
      o << ' ';
    }
    isBegin = false;
    o << e;
  }
  return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T> &v) {
  bool isBegin = true;
  for (auto &e : v) {
    if (!isBegin) {
      o << ' ';
    }
    isBegin = false;
    o << e;
  }
  return o;
}
template <class T>
ostream &operator,(ostream &o, const T &t) {
  return o << t;
}
struct StdinReader {
  StdinReader() { ios::sync_with_stdio(0); }
} stdinReader;
template <class T>
StdinReader &operator,(StdinReader &sr, T &t) {
  cin >> t;
  return sr;
}
template <class T>
StdinReader &operator,(StdinReader &sr, vector<T> &v) {
  for (auto &x : v) sr, x;
  return sr;
}
template <class T, class U>
StdinReader &operator,(StdinReader &sr, pair<T, U> &p) {
  return sr, p.first, p.second;
}
template <class T, class U>
bool remin(T &a, const U &b) {
  return b < a ? a = b, true : false;
}
template <class T, class U>
bool remax(T &a, const U &b) {
  return b > a ? a = b, true : false;
}
template <class T>
int size(const T &t) {
  return (int)t.size();
}
bool PWit(long long x, long long n) {
  if (x >= n) return 0;
  long long d = 1, y;
  int t = 0, l = n - 1;
  while (!(l & 1)) {
    ++t;
    l >>= 1;
  }
  for (; l > 0 || t--; l >>= 1) {
    if (l & 1) d = (d * x) % n;
    if (!l) {
      x = d;
      l = -1;
    }
    y = (x * x) % n;
    if (y == 1 && x != 1 && x != n - 1) return 1;
    x = y;
  }
  return x != 1;
}
bool IsPrime(int x) {
  return !(x < 2 || PWit(2, x) || PWit(61, x) || PWit(7, x));
}
int main() {
  int n;
  stdinReader, n;
  fancy_dumper::DumpFirst<&std::cout>(), IsPrime(n)       ? 1
                                         : !(n & 1)       ? 2
                                         : IsPrime(n - 2) ? 2
                                                          : 3;
}
