Once little Petya was learning positional numeral systems. Using such systems the numbers are represented as the sequence of digits

where b is the base of the numeral system, and 0 <= a_k < b. Petya was disappointed that one can represent only non-negative numbers this way. But then he found out that there are systems with negative base such as negabinary system in which b = −2, a_k ∈ {0, 1}. One can represent any integer in this system for example 1110₋₂ = −6. Moving the idea further Petya came up with his own base b using which he could represent even more numbers given a_k ∈ {0, 1}. However performing arithmetic operations in this non-standard system turned to be rather difficult. Help Petya implement a calculator for his numeral system.

Input

The first line of input is number T - the amount of test cases. Next T lines contain the description of arithmetic expression consisting of two operands and an operation separated with spaces. Both operands consist of one ‘0’ and ‘1’ digits and have the length of no more than 100. Operation is one of ‘+’, ‘-’ or ‘*’.

Constraints

1 <= T <= 1000

Output

For each test case output a number which is the result of evaluating the given expression.

Example

Input:
5
11 - 11
1 + 1
1100 * 1100
1101 - 11
111 * 1

Output:
0
1100
111010000
111010110
111