F

Sum of Totatives Input: Standard Input Output: Standard Output

When Tomisu's student Hedayet came to him with an open problem which he (Hedayet) thought was true after running a lengthy simulation, Tomisu's face lit up with a sense of glory. But soon his face dimmed because he was able to prove it within one day and the proof was a mere four liner (Such an easy and obvious proof will not bring glory). So now with a gloomy face he begins to write a contest problem (What else can he do after all?) which came to his mind as a bi-product of proving that theorem. Although as dumb as he is, he does not have any clue on how to solve this new problem, so he plans to ask Snapdragon for help. But before that he needs to write a crystal clear statement :). You may also help Tomisu solve this problem.

Let a ≥ 2 be a positive integer, then φ(a) denotes the number of "totatives" of a, i.e. those positive integers r < a such that (in other word gcd(r,a) equals 1). For example φ(25) = 20. There is another less known function titled "sum of totatives" which as the name indicates is the summation of these totatives. The symbol for this function is φ₁. For example φ₁(25) = 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + 12 + 13 + 14 + 16 + 17 + 18 + 19 + 21 + 22 + 23 + 24 = 250.

Now lets consider an equation φ₁(I) = M*φ₁(J), here I ≠ J and M is also a positive integer. Now given the value of M, you will have to find a possible value for I, J such that φ₁(I) = M*φ₁(J).

Input

The input file contains at most 400 lines of inputs. Each line contains a single positive integer which denotes the value of M. The value of M does not exceed 10⁹. For at least 80% cases the value of M does not even exceed 10⁸. Input is terminated by a line containing a single zero.

Output

For each set of input produce one line of output. This line contains three integers which denote the value of M, I and J respectively. The value of M will be such that either there will be possible values of I and J not exceeding 10¹⁶ or there will be no possible value of I and J. For the latter case print the line “No solution” (without the quotes) instead the value of I and J, but you need to print the value of M before that. You should make sure that (2 ≤ I, J ≤ 10¹⁶).

Sample Input Output for Sample Input

3 7 0

3 3 2 7 7 3

---

Problemsetter: Shahriar Manzoor, Moderator and alternate writer: Derek Kisman

Special Thanks: Mohammad Hedayet