import std.stdio;
import std.array;
import std.string;
import std.conv;
import std.algorithm;
import std.typecons;
import std.range;
import std.random;
import std.math;
import std.container;
import std.numeric;
import std.bigint;


bool is_prime(long x) {
  if (x <= 1 || x % 2 == 0) return false;
  long i = 3;
  while (i*i <= x) {
    if (x % i == 0)
      return false;
    i += 2;
  }
  return true;
}


void main() {
  auto N = readln.chomp.to!long;
  if (N == 2) writeln(1);
  else if (N == 3) writeln(1);
  else if (N == 5) writeln(1);
  else if (N % 2 == 0) writeln(2);
  else if (is_prime(N)) writeln(1);
  else if (is_prime(N-2)) writeln(2);
  else writeln(3);
}
