Euler's Totient Function 

Time-Limit: 5 second(s)

As you might know, Euler's totient function $\phi(n)$ is defined as the number of positive integers a, a ≤ n that are relatively prime to $n$. Two numbers are relatively prime if their greatest common divisor is 1. If the prime factorization of $n = p_1^{e_1}p_2^{e_2}\ldots p_j^{e_j}$ is known the value of $\phi(n)$ can be calculated via the following formula:

$$\Pi_{i = 1}^{j} (p_i-1)p_{i}^{e_i-1}$$

Now your task is to calculate the positive integers $n$ which fulfill the equation $\phi(n) = x$ for a given $x$.

Input
The input consists of a number of lines. On each line there is a single positve integer with no leading zeros. There are no spaces in the input. All numbers will be positive integers smaller than $1000000000$.

Output
For each line of input there should be one line of output. If the equation $\phi(n) = x$ has a solution, print all its solutions on a single line. The solutions should be printed in ascending order and should be seperated by a space. If there is no solution to the equation, print: No solution.

Sample Input

1
3
6

 

Sample Output

1 2
No solution.
7 9 14 18

 

Tilmann Spiegelhauer - FAU Local Winter Contest