生物学家矮人最近在弗罗茨瓦夫大学的民俗遗传学领域取得了突破性发现。经过多年的研究，他成功测序了居住在该市的三种不同物种的 DNA：矮人（他自己的种族）、侏儒（魔法森林居民）和青铜人（弗罗茨瓦夫街头传说中的青铜雕像人）。

每个 DNA 序列都表示为一个二进制字符串，其中 0 表示隐性遗传标记，1 表示显性遗传标记。他的目标是找到这三个物种共有的最长公共子序列（LCS）——这将揭示它们共同的进化祖先，并解释为什么它们最终都出现在弗罗茨瓦夫！然而，计算三个序列的精确 LCS 计算成本很高，而矮人的研究经费即将耗尽。他不需要绝对的精确度；他只需要找到一个整数 $x$，使得 3-LCS 的真实长度位于区间 $[x, 2x]$ 内。换句话说，一个 2-近似值就足够了。

这种近似值对于他的研究论文来说已经足够好，并且仍然能为弗罗茨瓦夫魔法居民的共同遗传遗产提供有价值的见解。你能帮矮人找到这样一个近似值吗？

输入格式

输入的第一行包含测试用例的数量 $T$。

每个测试用例包含四行。第一行包含一个整数 $N$，表示 DNA 序列的长度。接下来的三行包含长度为 $N$ 的二进制字符串，分别代表矮人、侏儒和青铜人的 DNA 序列。

输出格式

对于每个测试用例，输出一个整数 $x$，使得这三个 DNA 序列的最长公共子序列的长度位于区间 $[x, 2x]$ 内。

数据范围

$1 \le T \le 10$，$1 \le N \le 3\,000$，每个字符串仅由数字 0 和 1 组成。

样例

输入 1

2
4
0010
0110
0101
2
10
00
01

输出 1

2
1

说明 1

在第一个样例中，最优 LCS 为 010，其长度为 3。因此，答案 2 是正确的。