# D :: Prime Bases

Time Limit: 10 Seconds Memory Limit: 65536 KB

Given any integer base b >= 2, it is well known that every positive integer n can be uniquely represented in base b. That is, we can write

n = a_{0} + a_{1}*b + a_{2}*b*b + a_{3}*b*b*b + ...

where the coefficients a_{0}, a_{1}, a_{2}, a_{3}, ... are between 0 and b-1 (inclusive).

What is less well known is that if p_{0}, p_{1}, p_{2}, ... are the first primes (starting from 2, 3, 5, ...), every positive integer n can be represented uniquely in the "mixed" bases as:

n = a_{0} + a_{1}*p_{0} + a_{2}*p_{0}*p_{1} + a_{3}*p_{0}*p_{1}*p_{2} + ...

where each coefficient a_{i} is between 0 and p_{i}-1 (inclusive). Notice that, for example, a_{3} is between 0 and p_{3}-1, even though p_{3} may not be needed explicitly to represent the integer n.

Given a positive integer n, you are asked to write n in the representation above. Do not use more primes than it is needed to represent n, and omit all terms in which the coefficient is 0.

## Input

Each line of input consists of a single positive 32-bit signed integer. The end of input is indicated by a line containing the integer 0.

## Output

For each integer, print the integer, followed by a space, an equal sign, and a space, followed by the mixed base representation of the integer in the format shown below. The terms should be separated by a space, a plus sign, and a space. The output for each integer should appear on its own line.

## Sample Input

123 456 123456 0

## Sample Output

123 = 1 + 1*2 + 4*2*3*5 456 = 1*2*3 + 1*2*3*5 + 2*2*3*5*7 123456 = 1*2*3 + 6*2*3*5 + 4*2*3*5*7 + 1*2*3*5*7*11 + 4*2*3*5*7*11*13Submit

Source: Rocky Mountain 2008