Fed up using your operating system's stupid calculator and wanting for some recreation, you decide to make your own calculator. However, your everyday tasks revolve only around four operations: +, -, *, /. Furthermore, all the answers should be output modulo (10^9+7).

Input

The first line contains an integer T, the number of test cases. Each of the next T lines consists of an infix expression to be evaluated. The length of an expression won't exceed 100 characters.

Output

Output exactly T lines corresponding to each input test case. The output format for a particular test case should be of the form "Case #x: y", where x is the test-case number and y is the evaluated answer.

Example

Input:
2
10+5*3
10*9/4-5

Output:
Case #1: 25
Case #2: 17

Explanation

Case #1: * has a greater priority than +. So, 5*3 gets evaluated first.

Case #2: * and / have the same priority. Hence, we evaluate them from left to right. 10*9 will give 90. 90/4 will be 22 (truncate the non-integer part). And finally, 22-5 will result in 17.