题目描述

给定整数 $k$。存在一个由 $n$ 位二进制数构成的序列 $a_1,a_2,\dots,a_{2^k+1}$。其中 $a_1$ 与 $a_{2^k+1}$ 已知，其余位置数值未知。我们分 $k$ 轮按照如下规则填充所有未知数值：

第一，假设第 $i$ 轮开始前，已经填充完毕的下标为 $p_1 < p_2 < \dots < p_m$。第一轮开始前仅下标 $1,2^k+1$ 有数值。

第二，对每个 $j \in [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},\quad a_4 = a_3 \oplus a_5 = \texttt{010}$$

你需要计算表达式：

$$x_1 y_1 + x_2 y_2 + \dots + x_{2^k+1} y_{2^k+1}$$

其中 $x_i$ 表示 $a_i$ 中二进制位为 $\texttt{1}$ 的数量，$y_i$ 表示 $a_i$ 中二进制位为 $\texttt{0}$ 的数量。

注：$x \oplus y$ 表示两数按位异或。

输入格式

本题包含多组测试数据。第一行输入整数 $t$，满足

$$1 \le t \le 10^4,\quad 1 \le n \le 10^5,\quad 1 \le k \le 30$$

代表测试数据组数。

每组测试数据描述如下： 第一行两个整数 $n,k$，分别代表二进制数的位数、控制序列长度的参数。 第二行输入长度为 $n$ 的二进制字符串 $s$，代表 $a_1$。 第三行输入长度为 $n$ 的二进制字符串 $z$，代表 $a_{2^k+1}$。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对每组测试用例，输出题目中表达式的计算结果。

说明/提示

第一组测试用例的填充过程已在题目描述中给出，最终序列为 $[\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}$$

整个序列所有数均为 $0$，表达式结果为 $0$。

样例

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

10
0
3
12169074016