Problem Description

Town A has $\frac{(n+1)(n+2)}{2}$ intersections. These intersections are connected by $3n$ paths, forming an equilateral triangle whose side length contains $n$ roads. The case $n=3$ is shown in the figure below.

:::align{center} :::

These $3n$ paths can be divided into three directions: left-slanted, horizontal, and right-slanted. Each direction contains $n$ paths. In each direction, the $i$-th path consists of $i$ roads.

For example, when $n=3$:

• The left-slanted paths, ordered by the number of roads from small to large, are $(6\leftrightarrow9)$, $(3\leftrightarrow5\leftrightarrow8)$, $(1\leftrightarrow2\leftrightarrow4\leftrightarrow7)$.
• The horizontal paths, ordered by the number of roads from small to large, are $(2\leftrightarrow3)$, $(4\leftrightarrow5\leftrightarrow6)$, $(7\leftrightarrow8\leftrightarrow9\leftrightarrow10)$.
• The right-slanted paths, ordered by the number of roads from small to large, are $(4\leftrightarrow8)$, $(2\leftrightarrow5\leftrightarrow9)$, $(1\leftrightarrow3\leftrightarrow6\leftrightarrow10)$.

We call three distinct intersections $(u,v,w)$ an “equilateral triangle” triple of positive integer length $l$ if and only if, after arbitrarily reordering $u,v,w$, one of the following holds:

• Starting from $u$, go through $l$ left-slanted roads to reach $v$;
• Starting from $v$, go through $l$ horizontal roads to reach $w$;
• Starting from $w$, go through $l$ right-slanted roads to reach $u$.

Or:

• Starting from $u$, go through $l$ right-slanted roads to reach $v$;
• Starting from $v$, go through $l$ horizontal roads to reach $w$;
• Starting from $w$, go through $l$ left-slanted roads to reach $u$.

For example, in the figure above, $(2,4,5)$ and $(2,3,5)$ are “equilateral triangle” triples, while $(2,3,4)$ is not.

To reduce traffic congestion, Town A decides to assign a direction to every road. After directing the roads, each road has a unique fixed direction, and all roads on the same path share the same direction.

The figure below shows one possible orientation (corresponding to the third test case of Sample 1).

:::align{center} :::

We call three distinct intersections $(u,v,w)$ a “connected equilateral triangle” triple if and only if they form an “equilateral triangle” triple of positive integer length $l$ in the graph, and they can reach each other using only the $3l$ roads that form this “equilateral triangle” triple. For example, in the figure above:

• $(2, 4, 5)$ is a “connected equilateral triangle” triple, because it is not only an “equilateral triangle” triple, but also they can reach each other using only the roads of that triangle $(2 \rightarrow 4,4 \rightarrow 5, 5 \rightarrow 2)$.
• $(2, 3, 4)$ is not a “connected equilateral triangle” triple, because it is not an “equilateral triangle” triple.
• $(2, 3, 5)$ is not a “connected equilateral triangle” triple, because although it is an “equilateral triangle” triple, they cannot reach each other using only the roads of that triangle $(5 \rightarrow 3, 3 \rightarrow 2, 2 \leftarrow 5)$.

Now you are given the directions of all directed paths. Ask how many “connected equilateral triangle” triples there are in this graph.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

Then the test cases follow. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the equilateral triangle.

The second line contains a string $s1$ of length $n$, where $s1_i \in \{\text{0, 1}\}$. If $s1_i=\text{0}$, it means the direction of the left-slanted path consisting of $i$ roads is from upper-right to lower-left, and vice versa.

The third line contains a string $s2$ of length $n$, where $s2_i \in \{\text{0, 1}\}$. If $s2_i=\text{0}$, it means the direction of the horizontal path consisting of $i$ roads is from left to right, and vice versa.

The fourth line contains a string $s3$ of length $n$, where $s3_i \in \{\text{0, 1}\}$. If $s3_i=\text{0}$, it means the direction of the right-slanted path consisting of $i$ roads is from lower-right to upper-left, and vice versa.

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

Output Format

For each test case, output one integer, representing the number of “connected equilateral triangle” triples.

3
1
0
0
0
1
0
0
1
3
010
100
001

1
0
4

1
4
0011
1100
0011

6

Hint

In Sample 1, the graph of the first test case is shown below.

:::align{center} :::

In Sample 1, the graph of the second test case is shown below.

:::align{center} :::

In Sample 1, the “connected equilateral triangle” triples in the third test case are:

• $(2, 4, 5)$;
• $(4, 7, 8)$;
• $(5, 6, 9)$；
• $(2, 7, 9)$.

Translated by ChatGPT 5