cats 的电脑中毒

Problem Description

cats 的电脑被电脑病毒感染了。cats 的电脑可视为所有 $2^n$ 个长度为 $n$ 的，只包含 $0,1$ 两种字符的字符串的集合。每一个字符串为一个节点。如果两个节点的字符串之间有且仅有一个位置的字符不同，则认为这两个节点是相邻的。例如节点 $1111$ 和节点 $1110$ 是相邻的，但节点 $101$ 和节点 $000$ 不是相邻的。 在第 $0$ 秒时，电脑病毒感染了三个节点 $S_1,S_2,S_3$。从第 $1$ 秒开始，每一秒每个被电脑病毒感染的节点都会感染与它相邻的所有未被感染的节点。当所有节点都被感染时，cats 的电脑就损坏了。现在，你需要求出 cats 的电脑损坏的时间（按秒计算）。

Input

第一行包含一个整数 $T$ $(1\leq T \leq 10^4)$，表示一共有 $T$ 组测试数据。 每组测试数据的第一行为一个整数 $n$ $(2\leq n\leq 2\cdot 10^5)$，表示 cats 的电脑的节点的字符串长度。 接下来 $3$ 行，每行包含一个长为 $n$ 的，只包含 $0,1$ 两种字符的字符串 $S_i$，表示初始被电脑病毒感染的节点。保证对于任意的 $1\leq i < j\leq 3$，$S_i$ 与 $S_j$ 不完全相同。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一个整数，表示 cats 的电脑损坏的时间（按秒计算）。

Sample Input

4
2
01
10
11
3
011
000
110
7
1011001
0101110
0110100
10
0110110100
1100100010
0001110111

Sample Output

1
2
4
7

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）