题目描述

在这道题中，你需要解决一个简单的任务 -A 乘 $B$。

令 $U = \{a + b\sqrt{-2}|a, b \in \mathbb{Z}\}$ 为进行乘法运算的整个集合。显然，$U$ 中任何两个元素的乘积也是 $U$ 中的一个元素。

每个元素 $x \in U$ 在 $\sqrt{-2}$ 进制下可以表示为长度为 $n$ 的 01 字符串，形式为 $(c_{n-1}c_{n-2} \ldots c_0)_{\sqrt{-2}}$，其中 $x = \sum_{i=0}^{n-1} c_i \sqrt{-2^i}, \, c_i \in \{0,1\} \, (i = 0,1,\ldots,n-1)$ 且当 $n > 1$ 时有 $c_{n-1} = 1$。比如， $-1 + \sqrt{-2} = \sqrt{-2^0} + \sqrt{-2} + \sqrt{-2^2} = (111)_{\sqrt{-2}}$ 和 $2 - 4\sqrt{-2} = (4-2) + (-8+4)\sqrt{-2} = \sqrt{-2^2} + \sqrt{-2^4} + \sqrt{-2^5} + \sqrt{-2^7} = (10110100)_{\sqrt{-2}}$。

你的任务是计算 $U$ 中两个元素 $A$ 和 $B$ 在 $\sqrt{-2}$ 进制下的乘积。

输入格式

第一行包含一个整数 $T \, (1 \leq T \leq 10^5)$，表示测试用例的数量。

接下来是 $T$ 个测试用例。对于每个测试用例：

唯一的一行包含两个 01 字符串 $A$ 和 $B \, (|A|, |B| \geq 1, |A| + |B| \leq 2 \times 10^5)$。

保证 $T$ 个测试用例中 $(|A| + |B|)$ 之和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，在一行中输出一个 01 字符串，表示 $A$ 和 $B$ 在进制 $\sqrt{-2}$ 下的乘积。

5
0 1
10 10
10 11
101 101
110 110

0
100
110
1
10110100

解释 #1

对于样例的最后一个测试用例，$(-2 + \sqrt{-2})^2 = 2 - 4\sqrt{-2}$。