import math N = int(raw_input()) primes = [] nums = range(2,N+1) while nums: num = nums.pop(0) primes.append(num) if num > math.sqrt(N): primes += nums break else: nums = filter(lambda x:x%num!=0, nums) game = [True, True]+[False for _ in range(N-1)] for i in range(2,N+1): for j in filter(lambda x:x