The Game of the Century

Description:

Input:

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$$$.

Output:

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

Sample Input:

3
3
001
001
010
1
0
0
0
3
111
011
100

Sample Output:

2
0
3

Note:

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.