OWNCALC - Making your own Calculator

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.


Added by:Siddharth Kothari
Date:2010-10-25
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2013-01-01 22:35:35 Beta Projects
They go through all the trouble of providing a great system and then provide only dichotomous results of pass/fail. Instead show a percent correct and if above 98% correct, then provide the test cases that caused failure.

Last edit: 2013-01-01 22:36:06
2012-11-30 01:49:59 Hidder Zzz
There is no need to use bignum.
It's not specified, but operations are all modulo 1e9+7.

Last edit: 2012-11-30 01:50:21
2012-04-14 20:05:29 afonso
What is RNP?
2011-04-25 22:30:29 Jakub Stanecki
RNP+BIGNUM=TLE
2011-03-22 16:00:59 Krzysztof Butkiewicz
Could someone check the test cases - i'm using RNP algorithm (tested on bunch of cases found on the net) and i'm still getting WA :|
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.