F. Concise and clear
brute force; greedy; implementation; math
Vasya is a regular participant at programming contests and is already experienced in finding important sentences in long statements. Of course, numbers constraints are important — factorization of a number less than 1000000 is easier than of a number less than 1000000000. However, sometimes it's hard to understand the number at the first glance. Could it be shortened? For example, instead of 1000000 you could write \(10^{6}\), instead of 1000000000 —\(10^{9}\), instead of 1000000007 — \(10^{9}+7\).Vasya decided that, to be concise, the notation should follow several rules: the notation should only consist of numbers, operations of addition (""+""), multiplication (""*"") and exponentiation (""^""), in particular, the use of braces is forbidden; the use of several exponentiation operations in a row is forbidden, for example, writing ""2^3^4"" is unacceptable; the value of the resulting expression equals to the initial number; the notation should consist of the minimal amount of symbols. Given \(n\), find the equivalent concise notation for it.
The only line contains a single integer \(n\) (\(1 \leq n \leq 10\,000\,000\,000\)).
Output a concise notation of the number \(n\). If there are several concise notations, output any of them.
The third sample allows the answer 10^10 also of the length \(5\).