import math x = input() def isPrime(n): if n < 2: return 0 elif n == 2: return 1 for i in range(2, int(math.sqrt(n))+1): if not n % i: return 0 return 1 d=[-1,-1,-1,-1,3,-1,5,-1,7,7,7,-1,11,-1,13,7,7,-1,8,-1,19,19,7,-1,23,23,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,-1,8,14,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,14,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8] if x < 100: print d[x] else: a = x-1 b = x-8 flag = 0 for i in xrange(10000): if isPrime(i)==1: if b%i==0: flag = 1 if flag == 0: print 14 else: print 8