Назовем множество целых положительных чисел \(a_1, a_2, \dots, a_k\) квадратным, если произведение факториалов его элементов является квадратом целого числа, т. е. \(\prod\limits_{i=1}^{k} a_i! = m^2\), для некоторого целого \(m\).
Вам задано положительное целое число \(n\).
Ваша задача — для множества \(1, 2, \dots, n\) найти квадратное подмножество максимального размера. Если оптимальных ответов несколько, выведите любой из них.
Выходные данные
В первой строке выведите одно целое число — размер максимального подмножества. Во второй строке выведите само подмножество в произвольном порядке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
1
|
|
2
|
4
|
3
1 3 4
|
|
3
|
7
|
4
1 4 5 6
|
|
4
|
9
|
7
1 2 4 5 6 7 9
|