题目描述

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

输入

本题包含多组测试数据。 输入的第一行包含一个整数 $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}$ 不可以参与交换。

输出

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

输入样例

1
6
011101
111010
111010
101101

输出样例

4

提示

【样例 1 解释】 最开始时，$s_1$ = $011101$，第 $4$ 和第 $6$ 个字符不能参与交换；$s_2$ = $111010$，第 $2$ 和第 $5$ 个字符不能参与交换。 考虑如下操作：先交换 $s_{1,1}$ 与 $s_{1,2}$ 得到 $s_1 = 101101$，再交换 $s_{1,2}$ 与 $s_{1,3}$ 得到 $s_1 =110101$，最后交换 $s_{2,3}$ 与 $s_{2,4}$ 得到 $s_2 = 110110$。此时 $s_1$ 与 $s_2$ 的前 $4$ 个位置上的字符都是相同的。可以证明不存在更好的方案，故输出 $4$。 【数据范围】 对于所有的测试数据，保证：$1 ≤ T ≤ 10$，$1 ≤ n ≤ 10^5$。

测试点编号	n ≤	特殊性质
1 ∼ 4	10	无
5, 6	103	A
7, 8	105
9, 10	103	B
11, 12	105
13, 14	103	C
15, 16	105
17, 18	103	无
19, 20	105

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。