URI Online Judge | 2636

3-RSA

By Edson Alves da Costa Júnior, UNB BR Brazil

Timelimit: 1

Pedro, like many other undergraduates, was fascinated by the beauty and sophistication of cryptography. He began to read historical references, to study the main algorithms and to search for articles and news that approached the subject in the most different aspects.

However, the large volume of information gained in a short period of time has led to some questions and fears. Worried about quantum computing, which in theory would cripple RSA encryption, and motivated by the history of the DES algorithm, which had a more secure evolution called 3DES, he decided to propose a more secure version of RSA, called 3-RSA.

In 3-RSA, the module n, composed in the original algorithm by two distinct prime numbers, would now consist of 3 distinctly odd primes! Pedro was right that this modification would bring greater difficulty in breaking the algorithm, since the attackers now would have to find 3 factors of n, not only 2.

Knowing that in cryptography, sometimes less is more, and willing to show to the motivated and well-intentioned Peter that the proposed modification actually weakens the RSA, factor the n module of the 3-RSA algorithm, showing its three prime factors.

Input

The input consists of a series of test cases. Each test is represented by a single line, contains the integer n (105 ≤ n ≤ 1018), which represents the module of the 3-RSA algorithm. The input ends with the value n = 0, which should not be processed.

Output

For each test case a line containing the message ’n = p x q x r’ should be printed, where p, q, r are the prime factors of n, with 3 ≤ p x q x r.

Input Sample Output Sample

105

231

7163

89348965057411

0

105 = 3 x 5 x 7

231 = 3 x 7 x 11

7163 = 13 x 19 x 29

89348965057411 = 17393 x 51437 x 99871