给你一个整数$$$k$$$。有一个 $$$n$$$ 位二进制数 $$$a_1, a_2, \ldots, a_{2^k + 1}$$$ 的序列。数字 $$$a_1$$$ 和 $$$a_{2^k + 1}$$$ 是给你的,其他的未知。然后通过 $$$k$$$ 步骤如下填写未知数字:
- 假设在第 $$$i$$$ 步骤之前,索引为 $$$p_1 \lt p_2 \lt \ldots \lt p_m$$$ 的数字已经被填充。 (在第一步之前,这些数字的索引为 $$$1, 2^{k} + 1$$$)。
- 然后,对于从 $$$1$$$ 到 $$$m - 1$$$ 的每个 $$$j$$$,执行赋值 $$$a_{\frac{p_j + p_{j + 1}}{2}} := a_{p_j} \oplus a_{p_{j + 1}}$$$$$$^{\text{*}}$$$。
- 这些分配同时发生,之后所有这些数字也被填充。
可以看出,这个过程总是完全填满所有数字。
这就是 $$$k = 2$$$ 和 $$$n = 3$$$ 的过程,其中最初 $$$a_1 = \texttt{010}, a_5 = \texttt{110}$$$:
- 在第一步之前,填充索引为 $$$1, 5$$$ 的数字。因此,此操作将执行 $$$a_3 := a_1 \oplus a_5 = \texttt{010} \oplus \texttt{110} = \texttt{100}$$$。
- 在第二步之前,填充索引为 $$$1, 3, 5$$$ 的数字。因此,此操作将执行 $$$a_2 := a_1 \oplus a_3 = \texttt{110}$$$ 和 $$$a_4 = a_{3} \oplus a_{5} = \texttt{010}$$$
您需要计算以下表达式: $$$x_1 \cdot y_1 + x_2 \cdot y_2 + \ldots + x_{2^k + 1} \cdot y_{2^k + 1}$$$,其中 $$$x_i$$$ 是第 $$$i$$$ 中设置的位数,$$$y_i$$$ 是第 $$$i$$$ 个数字中零位的数量。
$$$^{\text{*}}$$$$$x \oplus y$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的按位异或
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n, k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 30$$$) — 二进制数的长度和确定序列中二进制数数量的数字。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i \in \{\texttt{0}, \texttt{1}\}$$$) — $$$a_1$$$ 的值。
每个测试用例的第三行包含一个长度为 $$$n$$$ 的二进制字符串 $$$z$$$ ($$$z_i \in \{\texttt{0}, \texttt{1}\}$$$) — $$$a_{2^k + 1}$$$ 的值。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个整数——语句中表达式的值。
示例
输入复制
43 20101101 1002 201007 3010101110011010
输出复制
100312169074016
注意
在第一个测试用例中,声明中描述了该过程。生成的二进制数序列为 $$$[\texttt{010}, \texttt{110}, \texttt{100}, \texttt{010}, \texttt{110}]$$$。那么语句中的表达式等于 $$$1 \cdot 2 + 2 \cdot 1 + 1 \cdot 2 + 1 \cdot 2 + 2 \cdot 1 = 10$$$。
在第二个测试用例中,第一步我们有 $$$a_2 = a_1 \oplus a_3 = \texttt{0} \oplus \texttt{0} = \texttt{0}$$$。因此,生成的数字序列为 $$$[\texttt{0}, \texttt{0}, \texttt{0}]$$$。对于它,表达式的值为零。