def miller_rabin_test(n): if n == 2: return True if n < 2 or n & 1 == 0: return False d = (n - 1) >> 1 while d & 1 == 0: d >>= 1 for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]: t = d y = pow(a, t, n) while t != n - 1 and y != 1 and y != n - 1: y = pow(y, 2, n) t <<= 1 if y != n - 1 and t & 1 == 0: return False return True N = int(input()) if N <= 26: print([0,0,0,0,3,0,5,0,7,7,7,0,11,0,13,7,7,0,8,0,19,19,7,0,23,23][N]) else: if N % 8 == 1 and miller_rabin_test(N - 8): print(14) else: print(8)