easy-calculation

Mathematics wrapped in English is not that Easy

Love stories that happened in college life stays for longer , even for a life-time. Ramanuj and Alice's love story is one of them. How they both fall for each-other only the past knows. 

Alice who was talented in English subject whereas Ramanuj was talented in Mathematics subject. After college they both got married with each-other. 

After years of their successful married life , Alice wanted to re-live their love story life when they were in college. She remember about the game they both had played very much.

The game was as simple as doing calculation in Mathematics. Alice used to write any Mathematical operation in English and Ramanuj used to solve it to impress her. For example , let say mathematical of '2 + 2' is written as '2PLUS2' in English , and the result is '4' .

After years Ramanuj can't solve Alice's question on his own , so he asked you for your help. Solve it for Ramanuj and Alice.

Input : First line will contains an integer T number of test cases. Next T lines will contain S ,  single string of operation you have to solve.

Output : Produce required output for each test case in new line.

Note : You have to follow Precedence Order of Operators. And final answer should be an integer. Output can be a large value so output your result as modulo 10^9

Constraints

1 ≤ T ≤ 100

SAMPLE INPUT
5
2PLUS2MULTIPLY6DIVIDE2MINUS1
21PLUS59MINUS94MINUS93MINUS15MULTIPLY50
66MINUS39MULTIPLY54DIVIDE32MINUS48MULTIPLY71
33PLUS41MULTIPLY15MULTIPLY83MULTIPLY52PLUS25
7DIVIDE7MULTIPLY84MINUS88MINUS7MULTIPLY39

SAMPLE OUTPUT
7
-857
-3407
2654398
-277

Explanation

Case 1 Explanation ,  Input String can be re-written as shown below (with spacing). Now when we follow the Precedence Order of Operators the below written steps shows the performed operation on given string. And at end we get 7 as our final result.

2 PLUS 2 MULTIPLY 6 DIVIDE 2 MINUS 1

2 PLUS 12 DIVIDE 2 MINUS 1

2 PLUS 6 MINUS 1

8 MINUS 1

7

If we solve the other cases according to Precedence Order of operators , we get the following results.

Case 2 : -857

Case 3 : -3407

Case 4 : 2654398

Case 5 : -277

Source: hackerearth | Difficulty: HARD


Solutions: