package main

import (
	"bufio"
	"fmt"
	"os"
)

func isPrime(n int64) bool {
	if n < 2 {
		return false
	}
	if n == 2 || n == 3 {
		return true
	}
	if n%2 == 0 || n%3 == 0 {
		return false
	}
	for i := int64(5); i*i <= n; i += 6 {
		if n%i == 0 || n%(i+2) == 0 {
			return false
		}
	}
	return true
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n int64
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	if isPrime(n) {
		fmt.Println(1)
		return
	}
	if n%2 == 0 {
		fmt.Println(2)
		return
	}
	if isPrime(n - 2) {
		fmt.Println(2)
		return
	}
	fmt.Println(3)
}