Let a
1 = 2, a
2 = 3, a
n = a
1·a
2 ·...·a
n-1 – 1 for n ≥ 3. We call the numbers ai pseudoprime. For a given natural number X, you need to answer the question: can X be uniquely represented as a product of pseudoprimes (representations that differ only in the order of factors are considered the same), and, if possible — output decomposition.<
Input
One natural number X, 1 < X≤ 10
9.
Imprint
Print pseudoprimes whose product equals X in any order. If the decomposition does not exist or it is not unique, return 0.
Examples
| # |
Input |
Output |
| 1 |
6 |
2 3 |
| 2 |
5 |
5 |
| 3 |
7 |
0 |