Let's call a set of positive integers a_1, a_2, ..., a_k quadratic if the product of the factorials of its elements is a square of an integer, i. e. ∏_{i=1}^{k} a_i! = m^2, for some integer m.

You are given a positive integer n.

Your task is to find a quadratic subset of a set 1, 2, ..., n of maximum size. If there are multiple answers, print any of them.

Input

A single line contains a single integer n (1 ≤ n ≤ 10^6).

Output

In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

Examples

Input


1


Output


1
1 


Input


4


Output


3
1 3 4 


Input


7


Output


4
1 4 5 6 


Input


9


Output


7
1 2 4 5 6 7 9

Difficulty: VERY_HARD
Tags: String algorithms

Number theory

Mathematics

Constructive algorithms

Starter code:

Solutions:
import random
import time
n = int(input())
n += 1
era = [0] * n
primes = []
for i in range(2, n):
	if era[i] == 0:
		primes.append(i)
		k = i
		while k < n:
			if era[k] == 0:
				era[k] = i
			k += i
hashes = {}
prime = {}
for guy in primes:
	r = random.randrange(0, 1 << 48)
	while r in prime:
		r = random.randrange(0, 1 << 48)
	hashes[guy] = r
	prime[r] = guy
hashall = [0, 0]
for i in range(2, n):
	xor = 0
	k = i
	while k > 1:
		p = era[k]
		i = 0
		while p == era[k]:
			k //= p
			i += 1
		if i % 2 == 1:
			xor ^= hashes[p]
	hashall.append(xor)
hashfac = [0, 0]
for i in range(2, n):
	hashfac.append(hashfac[-1] ^ hashall[i])
facmap = {}
for i in range(1, n):
	facmap[hashfac[i]] = i
total = 0
for i in range(1, n):
	total ^= hashfac[i]
if total == 0:
	print(n - 1)
	print(*[i for i in range(1, n)])
elif total in facmap:
	k = facmap[total]
	size = n - 2
	print(size)
	print(*[i for i in range(1, n) if i != k])
else:
	for i in range(1, n):
		x = total ^ hashfac[i]
		if x in facmap:
			j = facmap[x]
			print(n - 3)
			print(*[l for l in range(1, n) if l != i and l != j])
			break
	else:
		print(n - 4)
		print(*[i for i in range(1, n) if i != 2 and i != n - 1 and (i != (n - 2) // 2)])


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') is not None
if DEBUG:
	from inspect import currentframe, getframeinfo
	from re import search

def debug(*args):
	if not DEBUG:
		return
	frame = currentframe().f_back
	s = getframeinfo(frame).code_context[0]
	r = search('\\((.*)\\)', s).group(1)
	vnames = r.split(', ')
	var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
	prefix = f'{currentframe().f_back.f_lineno:02d}: '
	print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def batch_xor_hash(N):
	import random
	random.seed(123)
	MAX = (1 << 64) - 1
	pmap = {}
	hash = [0] * (N + 1)
	mpf = [0] * (N + 1)
	for i in range(2, N + 1):
		if mpf[i] == 0:
			pmap[i] = random.randint(0, MAX)
			hash[i] ^= pmap[i]
			mpf[i] = i
		for (p, h) in pmap.items():
			if p > mpf[i] or p * i > N:
				break
			mpf[p * i] = p
			hash[p * i] ^= hash[i] ^ h
	return (hash, pmap)

def solve(N):
	if N <= 3:
		return [1]
	(hash, _) = batch_xor_hash(N)
	xor = hf = 0
	lookup = {}
	for n in range(2, N + 1):
		hf ^= hash[n]
		xor ^= hf
		lookup[hf] = n
	if xor == 0:
		return list(range(1, N + 1))
	if xor in lookup:
		n = lookup[xor]
		debug(xor, n)
		return [i for i in range(1, N + 1) if i != n]
	for (h1, n1) in lookup.items():
		h2 = xor ^ h1
		if h2 in lookup:
			n2 = lookup[h2]
			return [i for i in range(1, N + 1) if i != n1 and i != n2]
	return [i for i in range(1, N) if i != 2 and i != N // 2]

def main():
	N = int(input())
	out = solve(N)
	print(len(out))
	print(*out)
main()