F. Квадратное множество
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем множество целых положительных чисел $$$a_1, a_2, \dots, a_k$$$ квадратным, если произведение факториалов его элементов является квадратом целого числа, т. е. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$, для некоторого целого $$$m$$$.

Вам задано положительное целое число $$$n$$$.

Ваша задача — для множества $$$1, 2, \dots, n$$$ найти квадратное подмножество максимального размера. Если оптимальных ответов несколько, выведите любой из них.

Входные данные

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

Выходные данные

В первой строке выведите одно целое число — размер максимального подмножества. Во второй строке выведите само подмножество в произвольном порядке.

Примеры
Входные данные
1
Выходные данные
1
1
Входные данные
4
Выходные данные
3
1 3 4
Входные данные
7
Выходные данные
4
1 4 5 6
Входные данные
9
Выходные данные
7
1 2 4 5 6 7 9