#!/usr/bin/env python3 import random def is_prime(n, k=20): # miller-rabin primality test if n == 2: return True if n == 1 or n % 2 == 0: return False d = n - 1 while d % 2 == 0: d //= 2 for _ in range(k): a = random.randint(1,n-2) t = d y = pow(a,t,n) while t != n-1 and y != 1 and y != n-1: y = (y * y) % n t <<= 1 if y != n-1 and t & 1 == 0: return False return True def bfs(n, w, initial, accept, deny=None): que = [initial] i = 0 pushed = set(que) while i < len(que): if accept(que, i): return True if deny is not None and deny(que, i): return False x = que[i] i += 1 def f(y): if y not in pushed and not is_prime(y): que.append(y) pushed.add(y) if x-1 > 0 and x % w != 1: f(x-1) if x+1 <= n and x % w != 0: f(x+1) if x-w > 0: f(x-w) if x+w <= n: f(x+w) def solve(n): if n < 300: # magic number for w in range(1,n): if bfs(n, w, 1, lambda que, i: que[i] == n): return w else: for w in range(2,n): if bfs(n, w, 1, lambda que, i: que[i] % w == 0) \ and bfs(n, w, n, lambda que, i: len(que) >= 10): # magic number return w print(solve(int(input())))