import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.math.BigInteger; import java.util.ArrayDeque; import java.util.BitSet; import java.util.HashMap; import java.util.Queue; public class Main { public static void main(String[] args) throws NumberFormatException, IOException {Solve solve = new Solve();solve.solve();} } class Solve{ void solve() throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner(); Writer out = new Writer(); // if(exp()) return; BigInteger bi = new BigInteger(in.readLine()); if(bi.compareTo(BigInteger.valueOf(40L))>=0){ if(bi.mod(BigInteger.valueOf(8)).equals(BigInteger.valueOf(1)) && bi.add(BigInteger.valueOf(8)).isProbablePrime(100)) System.out.println(14); else System.out.println(8); return; } BitSet p = prime(50); int n = bi.intValue(); for(int w=3; w qu = new ArrayDeque<>(); qu.add(0); BitSet used = new BitSet(h*w); while(!qu.isEmpty()){ int p = qu.poll(); if(used.get(p)) continue; used.set(p); if(goal==p) return true; final int y = p/w; final int x = p%w; for(int i=0; i<4; i++){ final int ny = dy[i]+y; final int nx = dx[i]+x; if(ny<0||ny>=h||nx<0||nx>=w||map[ny][nx]) continue; qu.add(ny*w+nx); } } return false; } public static BitSet prime(int max){ // こちらを使うように BitSet prime = new BitSet(max+1); prime.set(2, max+1); for(int i=2; i!=-1 && i*i<=max; i=prime.nextSetBit(i+1)) for(int j=i*2; j<=max; j+=i) prime.clear(j); return prime; } } class MultiSet extends HashMap{ @Override public Integer get(Object key){return containsKey(key)?super.get(key):0;} public void add(T key,int v){put(key,get(key)+v);} public void add(T key){put(key,get(key)+1);} } class Timer{ long time; public void set(){time = System.currentTimeMillis();} public long stop(){return System.currentTimeMillis()-time;} } class Writer extends PrintWriter{ public Writer(String filename) throws IOException {super(new BufferedWriter(new FileWriter(filename)));} public Writer() throws IOException{super(System.out);} } class ContestScanner { private BufferedReader reader; private String[] line; private int idx; public ContestScanner() throws FileNotFoundException {reader = new BufferedReader(new InputStreamReader(System.in));} public ContestScanner(String filename) throws FileNotFoundException {reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));} public String nextToken() throws IOException { if (line == null || line.length <= idx) { line = reader.readLine().trim().split(" "); idx = 0; } return line[idx++]; } public String readLine() throws IOException{return reader.readLine();} public long nextLong() throws IOException, NumberFormatException {return Long.parseLong(nextToken());} public int nextInt() throws NumberFormatException, IOException {return (int) nextLong();} public double nextDouble() throws NumberFormatException, IOException {return Double.parseDouble(nextToken());} }