Square Function

Time limit2sMemory limit256 MB

Summary

Given y, find every x whose S(x) equals y, where S(x) is the smallest last element of an increasing chain from x with a square product.

Level: Medium7 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

Let $S: \mathbb{N} \rightarrow \mathbb{N}$ be defined as follows. $S(x)$ is the smallest number for which there exists an increasing sequence of integers $x = t_1 < t_2 < \ldots < t_k = S(x)$ such that the product $t_1 \cdot t_2 \cdot \ldots \cdot t_k$ is a perfect square. For example, $S(2) = 6$ , $S(3) = 8$ , and $S(4) = 4$ .

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

Input

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

Output

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

Hint

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

Examples3

Example 1
Input
```
4
```
Expected output
```
1
4
```
Example 2
Input
```
5
```
Expected output
```
0
```
Example 3
Input
```
6
```
Expected output
```
1
2
```