Payment System

The payment system at the University of Mineral Water Production is fully automated (written entirely in the Tomato Programming Language) and lets you type in the amount of money you want to withdraw. Because the professors are paid so much, amounts may be entered in exponential form using the ^ operator. For example, to withdraw 16 MWU (mineral water units) you may enter 16, 2^4, or 2^2^2.

One day Stanescu, whose account held 80 MWU, entered 2^3^2 and to his surprise received 512 MWU, even though he should not have been able to take more than 80. The system has two modules: the first checks whether the account holds enough money for the transaction, and the second actually hands over the money. It turned out that the two modules disagree on the ^ operator. The first module evaluates it from left to right, while the second evaluates it from right to left (the mathematically correct way). So for the first module 2^3^2 = (2^3)^2 = 64, while for the second 2^3^2 = 2^(3^2) = 512.

Write a program that helps Stanescu withdraw as much as possible from the system. (If you think this is somehow not legal, rest assured that the University of Mineral Water Production is bad and evil.)

Each line of the input contains one amount held in Stanescu's account: an integer between 2 and 10^100 − 1. The input ends at end of file.

For each amount, print on its own line what Stanescu should enter in order to receive the greatest possible amount of money. The entry must:

• consist only of integers with the ^ operator between them;
• pass the check of the first module (its left-to-right value must not exceed the amount) while making the second module's value (evaluated right to left) as large as possible;
• not contain the number 1 (which is useless anyway).

If several entries give the same maximal amount, print the one whose first number is smallest; if there is still a tie, the one whose second number is smallest, and so on.