Towers of Powers 2: Power Harder

*Remark:* We were originally planning to give you
this in the real contest, but since we have too many awesome
problems for you for tomorrow and this one is just way too
easy, we decided to move it to the dress rehearsal as a sneak
preview.

In this problem we will be exploring the concept of sorting numbers. Most of you have likely written a sorting algorithm before, but just in case, here is a tutorial: You reorder the numbers to put the smaller ones in front and larger ones in the back.

Having dealt with the theory, we come to practice. You will be given some integers. Please output the same integers in sorted order. Where is the trick, you ask? Well, you might have to deal with equality cases. If two numbers are equal, the one that was the first in the input should also be the first on the output. Other than that, there are no tricks, no complications. Just sort the numbers from lowest to highest. Simple!

Oh, one more thing. When we say *some*
integers, we mean they might be somewhat large integers. To
make life easier for you, we will express them in a simple
“tower of powers” form. Each integer will be in the
format

where $1 \leq a_1, a_2, \ldots , a_ n \leq 100$, and $1 \leq n \leq 100$. Note that evaluation is from top to bottom, thus

\[ a_1^{a_2^{a_3}} = a_1^{\left(a_2^{a_3}\right)}. \]Are you done yet? No? Better start working!

The input consists of a single test case. The first line of
each test case contains the number $M$ of integers in this test case,
$1 \leq M \leq 100$. Each
of the next $M$ lines
describes one of the $M$
integers. The integer is written as described above, using the
caret (`^`) to represent power, with no whitespace.
There will be between $1$
and $100$ numbers in the
representation of each integer, and each of these numbers will
be an integer between $1$
and $100$.

Display the case number ($1$) followed by the sorted list of integers, one per line, in the original form.

Sample Input 1 | Sample Output 1 |
---|---|

4 2^2^2 3^4 15 9^2 |
Case 1: 15 2^2^2 3^4 9^2 |