题目描述

小三的三分球总是很准的.但对于数学问题就完全没有想法了，他希望你来帮他解决下面的这个问题:对于给定的$\red{n，}$从$\red{1!,2!,3!,...,n!}$中至少删去几个数，才可以使剩 下的数的乘积为完全平方数?

输入格式

输入一行一个整数$\red{n(1≤}$$\red{n≤}$$\red{500)}$。

输出格式

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

接下来一行,从小到大排列的$\red{k}$个$\red{[1,n]}$之间的整数,给出删数的方案。如果方案不 止一种,输出任意一组即可。

样例

输入样例

5

输出样例

2
2 5

提示

去掉$\red{2!}$和$\red{5!}$，剩下的是$\red{4!,3!}$和$\red{1!,}$它们的乘积为$\red{4! \times 3! \times 1! =24 \times 6=144}$。