9577: 咒语附魔

克利切洛夫斯基捡到了一个咒语，这个咒语可以看成一个长度为$N$的由0或1组成的数字串$A$（可以包含前导0），咒语的威力就是它本身对应的数字串看做二进制串时的的数值大小。克利切洛夫斯基希望威力越大越好，所以他又找到了一个长度为$M$的01数字串$B$来给咒语附魔。保证数字串$A$和$B$都是随机生成的，也就是说每个位置上的数字等概率地生成为0或1（由于采用C++ STL的rand函数生成伪随机数，所以并不能保证每一次随机都是互相独立的）。 在附魔时，克利切洛夫斯基可以任选$B$的一段长度为$N$的连续子串$B'$，将这段数字取出后与$A$进行异或，随后新的威力就变为$B' \oplus A$（$\oplus$为异或操作）转为十进制的结果，但他只能进行恰好一次附魔操作。请问他可能得到的最大的威力是多少？由于最终的结果可能很大，善良的克利切洛夫斯基只需要你输出附魔后威力最大的字符串中包含多少个1即可。 例如，初始咒语为$101$，用于附魔的数字串为$1100$。最优的策略是选择$110$这一段给初始咒语附魔，得到的咒语为$011$，转化为十进制后等于3，这是能够得到的最大威力。

本题单个测试点内包含多组测试数据。 输入第一行一个正整数 $T$ $(1 \leq T \leq 20)$，表示数据组数。 每组数据： - 第一行两个整数 $N$ $(1 \leq N \leq 200,000)$，$M$ $(1 \leq M \leq 200,000)$，分别表示$A$串的长度和$B$串的长度 - 第二行为长度为$N$的咒语数字串$A$ - 第三行为长度为$M$的附魔数字串$B$ 保证所有数据$M$的总和不超过$10^6$。

对于每一组测试数据，输出一行一个整数，表示选择的使附魔后威力最大的字符串中包含多少个1。

- $1 \leq N \leq 200,000$ - $1 \leq T \leq 20$ - $1 \leq M \leq 200,000$ - $N \leq M$ - 所有测试数据$M$的总和不超过$10^6$ - 输入字符串仅包含'0'和'1'