9721: Multiplication in base the Square Root of -2

In this problem, you are asked to solve an easy task -- $A$ multiplies $B$.

Let U= be the whole set where multiplications will be taken. Obviously, the product of any two elements in $U$ is also an element in $U$.

Each element $x\in U$ can be represented in base  as a 01-string of length $n$ in the form of , where x=  and when $n>1$, cn−1=1c_{n - 1} = 1cn−1=1. For example, −1+.

Your task is to calculate the product of two elements $A$ and $B$ of $U$ in base  representation.

The first line contains an integer $T$ (1<=T<=10⁵), indicating the number of test cases.
Then follow $T$ test cases. For each test case:
The only line contains two 01-strings $A$ and $B$ .
It is guaranteed that the sum of (∣A∣+∣B∣)(|A| + |B|)(∣A∣+∣B∣) over $T$ test cases does not exceed 2*10⁶.

For each test case, output a 01-string in one line, representing the product of $A$ and $B$ in base .

For the last test case of the example, .