Calculator#3187
Once, Petya was studying positional numeral systems. In such systems, numbers are represented as sequences of digits:
Here, is the base of the numeral system and 0 \leq a_{k} < b. Petya was disappointed that only non-negative numbers can be represented in this way. However, he discovered that there are numeral systems with a negative base, for example, the negabinary system, where b = -2 and a_{k} \in \{ 0, 1 \}. In such a system, all integers can be represented; for example, 1110_{-2} = -6. Developing this idea further, Petya invented his own system with base which allows even more numbers to be represented using a_{k} \in \{ 0, 1 \}. However, performing arithmetic operations in this non-standard system turned out to be rather difficult. Help Petya implement a calculator for his numeral system.
The first line contains (1 \leq T \leq 100) — the number of test cases. The following lines each contain an arithmetic expression, consisting of the first operand, the operation, and the second operand, separated by spaces. Both operands contain only the digits '0' and '1' and do not exceed characters in length. The operation is one of '+', '-', or '*'.
For each test case, output a single number — the result of the arithmetic operation.
Example 1