题目描述

给定一个整数 $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$ 的数。）
• 对于每个 $j$ 从 $1$ 到 $m - 1$，执行赋值 $a_{\frac{p_j + p_{j + 1}}{2}} := a_{p_j} \oplus a_{p_{j + 1}}$。
• 这些赋值同时进行，之后所有这些数也变为已填充。

可以证明该过程总能将所有数填充完整。

以下是 $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$ 个数中 $1$ 的个数，$y_i$ 是第 $i$ 个数中 $0$ 的个数。

$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$。

输出格式

对于每个测试用例，输出一个整数 —— 题目描述中表达式的值。

4
3 2
010
110
1 1
0
0
2 2
01
00
7 30
1010111
0011010

10
0
3
12169074016

提示

在第一个测试用例中，过程在题目描述中已有说明。最终得到的二进制数序列为 $[\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}]$，表达式的值为 $0$。