A. 编辑字符串
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

小 M 有两个长度为 $$$ n $$$ 且字符集为 $$$\{0, 1\}$$$ 的字符串 $$$ s_1, s_2 $$$。

小 M 希望两个字符串中对应位置字符相同的出现次数尽可能多，即满足 $$$ s_{1,i} = s_{2,i} $$$ 的 $$$ i(1 \leq i \leq n) $$$ 尽可能多。为此小 M 有一个字符串编辑工具，这个工具提供的基本操作是在一个字符串中交换两个 相邻 的字符。为了保持字符串的可辨识性，规定两个字符串中的部分字符不能参与交换。小 M 可以用工具对 $$$ s_1 $$$ 或 $$$ s_2 $$$ 进行多次字符交换，其中可以参与交换的字符能够交换任意多次。

现在小 M 想知道，在使用编辑工具后，两个字符串中对应位置字符相同的出现次数最多能有多少。

Input

$$$\textbf{本题包含多组测试数据。}$$$

输入的第一行包含一个整数 $$$T$$$，表示测试数据的组数。

接下来包含 $$$T$$$ 组数据，每组数据的格式如下：

  • 第一行包含一个整数 $$$n$$$，表示字符串长度。
  • 第二行包含一个长度为 $$$n$$$ 且字符集为 $$$\{0, 1\}$$$ 的字符串 $$$s_1$$$。
  • 第三行包含一个长度为 $$$n$$$ 且字符集为 $$$\{0, 1\}$$$ 的字符串 $$$s_2$$$。
  • 第四行包含一个长度为 $$$n$$$ 且字符集为 $$$\{0, 1\}$$$ 的字符串 $$$t_1$$$，其中 $$$t_{1,i}$$$ 为 $$$1$$$ 表示 $$$s_{1,i}$$$ 可以参与交换，$$$t_{1,i}$$$ 为 $$$0$$$ 表示 $$$s_{1,i}$$$ 不可以参与交换。
  • 第五行包含一个长度为 $$$n$$$ 且字符集为 $$$\{0, 1\}$$$ 的字符串 $$$t_2$$$，其中 $$$t_{2,i}$$$ 为 $$$1$$$ 表示 $$$s_{2,i}$$$ 可以参与交换，$$$t_{2,i}$$$ 为 $$$0$$$ 表示 $$$s_{2,i}$$$ 不可以参与交换。
Output

对于每组测试数据输出一行，包含一个整数，表示对应的答案。

Example
Input
1
6
011101
111010
111010
101101
Output
4
Note

$$$\textbf{【样例 1 解释】}$$$

最开始时，$$$s_1 = \tt{011101}$$$，第 $$$4$$$ 和第 $$$6$$$ 个字符不能参与交换；$$$s_2 = \tt{111010}$$$，第 $$$2$$$ 和第 $$$5$$$ 个字符不能参与交换。

考虑如下操作：先交换 $$$s_{1,1}$$$ 与 $$$s_{1,2}$$$ 得到 $$$s_1 = \tt{101101}$$$，再交换 $$$s_{1,2}$$$ 与 $$$s_{1,3}$$$ 得到 $$$s_1 = \tt{110101}$$$，最后交换 $$$s_{2,3}$$$ 与 $$$s_{2,4}$$$ 得到 $$$s_2 = \tt{110110}$$$。此时 $$$s_1$$$ 与 $$$s_2$$$ 的前 $$$4$$$ 个位置上的字符都是相同的。可以证明不存在更好的方案，故输出 $$$4$$$。

$$$\textbf{【样例 2 解释】}$$$

见附件的 edit/edit2.in 与 edit/edit2.ans。

该样例共有 $$$10$$$ 组测试数据，其中第 $$$i(1 \leq i \leq 10)$$$ 组测试数据满足数据范围中描述的测试点 $$$2i - 1$$$ 的限制。

$$$\textbf{【数据范围】}$$$

对于所有的测试数据，保证：$$$1 \leq T \leq 10$$$，$$$1 \leq n \leq 10^5$$$。

测试点编号$$$n\leq$$$特殊性质
$$$1\sim 4$$$$$$10$$$无
$$$5,6$$$$$$10^3$$$A
$$$7,8$$$$$$10^5$$$A
$$$9,10$$$$$$10^3$$$B
$$$11,12$$$$$$10^5$$$B
$$$13,14$$$$$$10^3$$$C
$$$15,16$$$$$$10^5$$$C
$$$17,18$$$$$$10^3$$$无
$$$19,20$$$$$$10^5$$$无

  • 特殊性质 A：保证 $$$s_1$$$ 的所有字符相同。
  • 特殊性质 B：保证 $$$t_1 = t_2$$$。
  • 特殊性质 C：保证 $$$t_1$$$ 和 $$$t_2$$$ 中各自恰有一个字符 $$$\tt 0$$$。