package puzzle.yukicoder.primeimpassable;

import java.math.BigInteger;
import java.util.Scanner;

public class PrimeImpassable {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long n = Long.parseLong(cin.next());
        cin.close();
        int w;
        /*
         * wを1から順に考える。
         * w=1のときは縦1列、隣接マスが素数である2しかないので移動できない。
         * w=2のときは、隣接マスが素数である2と3であるため移動できない。
         * w=3のときは、隣接マスが2と4なので、4に移動できる。しかし4に隣接するマスが素数である5と7のため、それ以上は移動できない。ただし、N=4のときはw=3で成立する。
         * w=4のときは、隣接マスが素数である2と5であるため移動できない。
         * w=5のときは、隣接マスが2と6なので、6に移動できる。しかし6に隣接するマスが素数である7と11のため、それ以上は移動できない。ただし、N=6のときはw=5で成立する。
         * w=6のときは、隣接マスが素数である2と7であるため移動できない。
         * w=7のときは、隣接マスが2と8なので、8に移動できる。そのまま9,16,25,26,33,34,35と移動していくことで、一番右の列に到達できる。一番右の列は7の倍数列なので素数が現れることはない。
         * w=8のときは、隣接マスが2と9なので、9に移動できる。そのまま10に移動すると、そこから10に移動すると、wが偶数なので、10の列はどこまでも偶数が続く。
         * w=9のときは、隣接マスが2と10なので、10に移動できる。しかし10に隣接するマスが素数である11と19のため、それ以上は移動できない。N=10のときはw=9で成立するが、w=7でも成立するため解ではない。
         * 以上を考慮すると、N=4のときとN=6のときだけ特殊扱いとし、それ以上の数字の場合の大半でw=7が解となり、w=7が解とならない場合にはw=8が解となりそうである。
         * w=7が解にならないのは、Nの1つ前の値とN-7がどちらも素数、すなわち、左からも上からもNに到達できない場合である。
         */
        if(n==4){
            w=3;
        }else if(n==6){
            w=5;
        }else if(isPrime(n-1) && isPrime(n-7)) {
            w=8;
        } else{
            w=7;
        }
        System.out.println(w);
    }

    private static boolean isPrime(long n) {
        /* 素数判定はBigIntegerのメソッドに任せる */
        BigInteger bi = new BigInteger(String.valueOf(n));
        return bi.isProbablePrime(8);
    }

}