题目描述

小三的三分球总是很难的，但对于数学问题就完全没有想法了，他希望你来帮他解决下面的这问题：对于给定的n,从1!,2!,3!…,n!中删去几个数，才可以使剩下的数的乘积为完全平方数？

输入格式

输入一行一个整数n

输出格式

输出第一行包含一个整数k ,表示最少需要删去的数字个数。

接下来一行,从小到大排列的k个[1,n]之间的整数,给出删数的方案。如果方案不止一种，输出方案从小到大排序序列最小的一组即可。

样例

5

2
2  5

样例解释

去掉2!和5!,剩下的是4!,3!和1!,它们的乘积为4! * 3! * 1!=24*6=144。

数据范围

$1 \le n \le 500$

来源

• 信息学奥赛之数学一本通
• stong9070整理