Yuri 被赋予两个二进制字符串 $$$a$$$ 和 $$$b$$$,两者的长度都是 $$$n$$$。这两个字符串动态定义一个 $$$n \times n$$$ 网格。让 $$$(i, j)$$$ 表示第 $$$i$$$ 行和 $$$j$$$ 列中的单元格。单元格$$$(i, j)$$$的初始值为$$$a_i \oplus b_j$$$,其中$$$\oplus$$$表示按位异或运算。 。
尤里的旅程总是从单元格$$$(1, 1)$$$开始。从单元格 $$$(i, j)$$$ 开始,她只能向下移动到 $$$(i + 1, j)$$$ 或向右移动到 $$$(i, j + 1)$$$。如果存在一条有效路径,且该路径上的所有单元格(包括 $$$(1, 1)$$$)的值为 0,则她的旅程是可能的。
出发前,她可以进行任意次数的以下操作:
- 选择一个索引 $$$1 \le i \le n$$$,然后翻转 $$$a_i$$$ 或 $$$b_i$$$ 的值($$$0$$$ 变为 $$$1$$$,$$$1$$$ 变为 $$$0$$$)。网格也会相应改变。
让 $$$f(x, y)$$$ 表示 Yuri 能够前往单元格 $$$(x,y)$$$ 所需的最少操作。您必须确定 总和 的 $$$f(x, y)$$$ 超过所有 $$$1 \leq x, y \leq n$$$。
请注意,这些 $$$n^2$$$ 情况中的每一个都是独立的,这意味着您需要假设网格在每种情况下都处于其原始状态(即,不执行任何实际操作)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含一个二进制字符串 $$$a$$$ ($$$|a| = n$$$, $$$a_i \in \{0, 1\}$$$)。
每个测试用例的第三行包含一个二进制字符串 $$$b$$$ ($$$|b| = n$$$, $$$b_i \in \{0, 1\}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——所有可能单元格的最小运算之和。
示例
输入复制
32110020101410101101
输出复制
5 4 24
注意
在第一个测试用例中,$$$2 \times 2$$$ 网格如下所示。
$$11 \\ 11$$
在初始状态下,尤里无法到达任何单元格。
Yuri 可以翻转 $$$a_1$$$,使网格变为:
$$00 \\ 11$$
和尤里可以前往单元格$$$(1,1)$$$和$$$(1,2)$$$。
另一方面,Yuri 可以翻转 $$$b_1$$$,使网格变为:
$$01 \\ 01$$
和 Yuri 可以前往单元格 $$$(1,1)$$$ 和 $$$(2,1)$$$。
要移动到单元格$$$(2,2)$$$,可以表明她必须执行至少两个操作。例如,她可以翻转 $$$a_1$$$ 和 $$$a_2$$$,使网格变为:
$$00 \\ 00$$
因此,答案是$$$1+1+1+2=5$$$。