CF1779G.The Game of the Century

The time has finally come, MKnez and Baltic are to host The Game of the Century. For that purpose, they built a village to lodge its participants.

The village has the shape of an equilateral triangle delimited by three roads of length $n$. It is cut into $n^2$ smaller equilateral triangles, of side length $1$, by $3n-3$ additional roads which run parallel to the sides. See the figure for $n=3$. Each of the $3n$ roads is made of multiple (possibly $1$) road segments of length $1$ which connect adjacent intersections.

The direction has already been chosen for each of the $3n$ roads (so, for each road, the same direction is assigned to all its road segments). Traffic can only go in the specified directions (i. e. the roads are monodirectional).

You are tasked with making adjustments to the traffic plan so that from each intersection it is possible to reach every other intersection. Specifically, you can invert the traffic direction of any number of road segments of length $1$. What is the minimal number of road segments for which you need to invert the traffic direction?

万众期待的时刻终于到来，MKnez 与 Baltic 即将主办“世纪之战”。为此，他们专门建造了一座村庄，用于接待参赛者。

该村庄呈等边三角形形状，由三条长度均为 $n$ 的道路围成。通过另外 $3n-3$ 条与三角形各边平行的道路，整个村庄被划分为 $n^2$ 个边长为 $1$ 的更小等边三角形（参见 $n=3$ 时的示意图）。这 $3n$ 条道路中的每一条均由若干段（可能仅有一段）长度为 $1$ 的路段组成，这些路段连接相邻的交叉路口。

目前，每条长度为 $n$ 的道路均已预先指定了单一通行方向（即：该道路上所有长度为 $1$ 的路段均按同一方向通行）。车辆只能沿指定方向行驶（即所有道路均为单向）。

你的任务是对当前交通方案进行调整，使得从任意一个交叉路口出发，均可到达其余任意交叉路口。具体而言，你可以任意选择若干段长度为 $1$ 的路段，并将其通行方向取反。问：最少需要取反多少段长度为 $1$ 的路段？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows.

The first line of each test case contains a positive integer $n$ ($1\leq n\leq 10^5$) — the size of the triangular village's sides.

Three lines follow, each containing a binary string of length $n$ which describes the traffic directions of the roads.

The $i$-th of the following three lines contains a binary string $s_i$ of length $n$ representing the direction of each road parallel to the road segment denoted by $i$ in the picture above. In particular, the $j$-th character of $s_i$ is "1" if the $j$-th shortest road (parallel to the road segment denoted by $i$ in the picture) has the same direction of the road segment denoted by $i$ in the picture, while it is "0" if it has the opposite direction. So the first character of $s_i$ describes the direction of the road containing only $1$ road segment, while the last character describes the direction of the road containing $n$ road segments.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 10\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$（$1\leq n\leq 10^5$）——表示三角形村庄各边的长度。

接下来有三行，每行包含一个长度为 $n$ 的二进制字符串，用于描述道路的通行方向。

接下来的三行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $s_i$，表示图中编号为 $i$ 的道路段所在方向上的所有道路的通行方向。具体而言，$s_i$ 的第 $j$ 个字符为 "1"，表示与图中编号为 $i$ 的道路段平行的、第 $j$ 短的道路（即包含 $j$ 段道路的道路）的方向与图中编号为 $i$ 的道路段方向相同；若为 "0"，则表示方向相反。因此，$s_i$ 的第一个字符描述的是仅含 $1$ 段道路的那条道路的方向，而最后一个字符描述的是含 $n$ 段道路的那条道路的方向。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, print the minimum number of road segments for which you need to invert the traffic direction.

对于每个测试用例，输出需要反转交通方向的最少道路段数。

The first example corresponds to the picture in the statement. There exist multiple solutions that invert the traffic direction of exactly $2$ road segments, but inverting only $1$ road segment never makes it possible to reach every intersection from any other. One of the possible solutions is shown in the picture below in which the inverted road segments are highlighted in blue.

In the second example, the answer is $0$ since it is already possible to reach every intersection from any other.

第一个示例对应题目描述中的图片。存在多种方案，恰好将 $2$ 条道路的通行方向取反，即可满足要求；但仅取反 $1$ 条道路的方向永远无法实现从任意交叉口均可到达其余所有交叉口。下图展示了一种可能的解法，其中被取反的道路段以蓝色高亮显示。

在第二个示例中，答案为 $0$，因为当前图中已可实现从任意交叉口到达其余所有交叉口。