Prime Factors

Webster defines prime as:

prime (prim) n. [ME, fr.MF, fem.of prin first, L primus; akin to L prior] 1 : first in time: original 2 a : having no factor except itself and one < 3 is a ~ number > b : having no common factor except one < 12 and 25 are relatively ~> 3 a: first in rank, authority or significance : principal b : having the highest quality or value <~ television time > [from Webster's NewCollegiate Dictionary]

The most relevant definition for this problem is 2a: An integer g >1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e.,

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2^p- 1. Euler proved that 2³¹ - 1 is prime in 1772 — all without the aid of a computer.

Input

The input will consist of a sequence of numbers. Each line of input will contain one number g in the range - 2³¹< g < 2³¹ . The end of input will be indicated by an input line having a value of zero.

Output

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number 0 < g = f₁ x f₂ x... x f_n, where each f_i is a prime number greater than unity (with f_i <= f_j for i < j), the format of the output line should be

For an input number 0 > g = f₁ x f₂ x... x f_n,, the format of the output line should be

Example

The following is sample input for this problem.

-190

-191

198

The following is the corresponding output for the input above.

-190 = -1 x 2 x 5 x 19

-191 = -1 x 191

198 = 2 x 3 x 3 x 11