시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 4 3 2 66.667%

문제

Let us define function $S$: $\mathbb{N} \rightarrow \mathbb{N}$ in the following way: $S(x)$ is the minimum number for which there exists an increasing sequence of integers $x = t_{1} < t_{2} < \ldots < t_{k} = S(x)$ such that $t_{1} \cdot t_{2} \cdot \ldots \cdot t_{k}$ is a square of some integer. For example, $S(2) = 6$, $S(3) = 8$, $S(4) = 4$.

Given $y$, find all such $x$ that $S(x)=y$.

입력

The only line of input contains a single integer $y$ ($1 \le y \le 10^{6}$).

출력

On the first line, print the number of solutions. On the second line, list all solutions in increasing order separated by spaces.

예제 입력 1

4

예제 출력 1

1
4

예제 입력 2

5

예제 출력 2

0

예제 입력 3

6

예제 출력 3

1
2

힌트

$\mathbb{N}$ is the set of positive integers.