ADV04K - Calculator

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

an an−1 … a2 a1 a0
 = 
n
k=0
 ak bk,

where b is the base of the numeral system, and 0 <= ak < 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, ak ∈ {0, 1}. One can represent any integer in this system for example 1110−2 = −6. Moving the idea further Petya came up with his own base b using which he could represent even more numbers given ak ∈ {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

Added by:Spooky
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin

hide comments
2019-07-26 04:43:11
Need an explanation for the output when 1+1 =0010(base2) since output should be in base-2 then output should show 1010 why 1100
2011-04-17 21:50:08 Anshul Gupta
i am getting WA..any hints???
2010-11-26 09:21:43 :D
Make an equasion from second example and you will have two candidates for the base.
2010-11-26 04:41:57 Lukmanul Hakim
Are the base in real set? Or in imaginary set too?
2010-11-25 17:46:54 Spooky
It's not base -2:
"Moving the idea further Petya came up with his own base b using which he could represent even more numbers given ak ∈ {0, 1}."
2010-11-25 10:49:33 -=^_^yos}{imori^_^=-
correct me if i am wrong,
all the above numbers :1101,11,1 are represented in -2 base right?
if so,
as 1 in (base: -2) is same as 1 in (base: 10).
then 1+1 adding to 2 is represented as 110 in (base -2).then how can the output be 1100?

similarly, 1101-11 is 10... how is it 111010110?

Last edit: 2010-11-25 10:52:14
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.