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 def isPrime2(q,k=100000): q = abs(q) if q == 2: return 1 if q < 2 or q&1 == 0: return 0 for i in xrange(3,k): x,y = q,i while y: x, y = y, x % y if x != 1: continue if pow(i, q-1, q) != 1: return 0 return 1 def gcd(a, b): if b == 0: return a return gcd(b, a % b) 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 b = x-8 if (a-1)%8==0: if isPrime2(b)==1: print 14 else: print 8 else: print 8