Camel Trading

In around 800 AD, El Mamum, Calif of Baghdad, was presented the formula 1+2*3*4+5, which had its origin in the financial accounts of a camel transaction. The formula lacked parentheses and was ambiguous. So, he decided to ask savants to provide him with a method to find which interpretation is the most advantageous for him, depending on whether he is buying or selling the camels.

You are commissioned by El Mamum to write a program that determines the maximum and minimum possible interpretation of a parentheses-less expression.

Input Specification

The input consists of an integer N, followed by N lines, each containing an expression. Each expression is composed of at most 12 integers, each ranging between 1 and 20, separated by the sum and product operators + and *.

Output Specification

For each given expression, the output should echo a line with the corresponding maximal and minimal interpretations, following the format given in the sample output.

Sample Input

1. 3
2. 1+2*3*4+5
3. 4*18+14+7*10
4. 3+11+4*1*13*12*8+3*3+8

download as text file

Output for Sample Input

1. The maximum and minimum are 81 and 30.
2. The maximum and minimum are 1560 and 156.
3. The maximum and minimum are 339768 and 5023.

download as text file