The payment system in the University of Mineral Water Production is completely automated (written entirely in Tomato Programming Language) and lets you input the amount of money you want to withdraw. Due to the high payment rates of the professors they may input the amounts in exponential forms. So if you want to withdraw 16 MWU (mineral water units) you can enter 16, 24 or 222.
One day, Stanescu tried to withdraw some money from his account which had balance of 80MWU. He mistakenly entered 232 and for his surprise he got 512MWU, although he should not be able to take more than 80. The system was composed of two main modules – the first module checks whether the account has enough money to execute the transaction and the second module gives the money to the user. It turned out that the first module has a problem with the '' operator. It evaluates it from left to right, while the second evaluates them from right to left (the correct way). Thus for the first module 232=(23)2=64 while for the second it's 232=232=512.
You have to write program which helps Stanescu get as much as he can from the university system. If you think it's not legal or something, be sure that the University of Mineral Water Production is bad and evil.
In the input file the amounts of the accounts of Stanescu will be given. Each amount is given on a separate line and is an integer between 2 and 10100-1.
For each given amount, your program should print to the standard output what Stanescu should enter to get maximal number of money. The output should:
16 80 49 1025 12341234 12345678901234567890
2^2^2 2^3^2 7^2 2^2^5 2^2^2^5 2^2^2^2^3^2
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|