LISA  Pocket Money
Young people spend a lot of money on things like sweets, music CDs, mobile phones and so on. But most young girls/boys have one problem: Their pocket money is not enough for all these jolly things. Little Lisa Listig is one of these poor girls with a small pocket money budget. Last month her pocket money lasted only one week. So she decided to enter into negotiations with her father. Her father Tomm  a mathematician  had an incredibly ingenious idea: He wrote down some fancy digits with operators (+,*) in between them on a sheet of paper and allowed Lisa to insert brackets. Then he declared that the result of that arithmetic expression is Lisa's new pocket money. Now it's Lisa's task to maximize her pocket money. As her father was surprised what a huge sum of money Lisa got for her result, he decided to minimize the result of the expression for his son Manfred. Now it's your task to calculate the results obtained by Lisa and her father.
Input
The first line of input contains the number of testcases k ( k< 5000 ). Each of the following k lines consists of an arithemtic expression. This expression consists of numbers (09) seperated by one of the two operators '*' and '+'. There are no spaces between the characters. Each line contains less than 100 characters.
Output
For each expression output the result obtained by Lisa and the result obtained by her father separated by one space. The results of the calculations are smaller than 2^{64}.
Example
Input: 1 1+2*3+4*5 Output: 105 27
Two possible expressions for the first testcase:
105 = (1+2)*(3+4)*5 27 = 1+2*3+4*5
hide comments
probito:
20201221 14:16:56
AC after 8 months. Understood MCM properly now 

oreoshake:
20201113 15:40:43
so many AC's in 1 go....lol just makes me laugh 

aakash9518:
20200918 09:28:11
@sfialok98 Thanks for the test case! 

prasannabhat01:
20200820 08:13:15
where can we get to know about failed test case for our code


coolio_1:
20200302 18:14:18
AC in 1 Go! 

dkkv0000:
20200120 05:09:09
2 times (mcm) easy peasy TOP DOWN 0.11 

assasin123:
20190118 18:02:42
simple question. just read MCM once then you can do it in one go.... i got AC in one go


manishjoshi394:
20181114 08:23:04
@sharif ullah's comment is the most helpful guys.


gormint7777:
20180928 17:47:59
sharif ullah's comment is a real helper _/\_


sharif ullah:
20180521 21:43:32
so,like people i would like to say,,,,it nothing but a recursive problem ,,more formally a matrxi chain multiplication problem... if u dont get idea to solve it THINK ABOUT THE problem ,,,scretch how MCM works,,,,TRUST me Though u think about a girl whole day or month she may be reject ur love!!!! but thinking about programming problem never frustrate u.... Last edit: 20180521 21:48:54 
Added by:  Simon 
Date:  20050517 
Time limit:  32s 
Source limit:  8082B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL GOSU JSRHINO 
Resource:  Ulm Algorithm Course SoSe 2005 