Town A has $\frac{(n+1)(n+2)}{2}$ intersections, which are connected by $3n$ paths to form an equilateral triangle with a side length of $n$ roads. The case for $n=3$ is shown in the figure below:

These $3n$ paths can be divided into three orientations: left-diagonal, horizontal, and right-diagonal, with each orientation containing $n$ paths. The $i$-th path of each orientation consists of $i$ roads. For example, when $n=3$:

• The left-diagonal paths, ordered by the number of roads from fewest to most, are $(6 \to 9)$, $(3 \to 5 \to 8)$, and $(1 \to 2 \to 4 \to 7)$.
• The horizontal paths, ordered by the number of roads from fewest to most, are $(2 \to 3)$, $(4 \to 5 \to 6)$, and $(7 \to 8 \to 9 \to 10)$.
• The right-diagonal paths, ordered by the number of roads from fewest to most, are $(4 \to 8)$, $(2 \to 5 \to 9)$, and $(1 \to 3 \to 6 \to 10)$.

We call three distinct intersections $(u, v, w)$ a "positive triangle" intersection of length $l$ (where $l$ is a positive integer) if and only if, after reordering $u, v, w$ in any way, we can satisfy:

• Traveling from $u$ through $l$ left-diagonal roads reaches $v$;
• Traveling from $v$ through $l$ horizontal roads reaches $w$;
• Traveling from $w$ through $l$ right-diagonal roads reaches $u$.

Or:

• Traveling from $u$ through $l$ right-diagonal roads reaches $v$;
• Traveling from $v$ through $l$ horizontal roads reaches $w$;
• Traveling from $w$ through $l$ left-diagonal roads reaches $u$.

For example, in the figure above, $(2, 4, 5)$ and $(2, 3, 5)$ are "positive triangle" intersections, while $(2, 3, 4)$ is not.

To prevent traffic congestion, Town A has decided to orient every road. After orientation, each road has a unique fixed direction, and all roads on the same path have the same direction.

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

• $(2, 4, 5)$ is a "connected positive triangle" intersection. This is because they are not only a "positive triangle" intersection, but they can also reach each other using the roads of this "positive triangle" intersection $(2 \to 4, 4 \to 5, 5 \to 2)$.
• $(2, 3, 4)$ is not a "connected positive triangle" intersection because they do not form a "positive triangle" intersection.
• $(2, 3, 5)$ is not a "connected positive triangle" intersection. Although they form a "positive triangle" intersection, they cannot reach each other using the roads of this "positive triangle" intersection $(5 \to 3, 3 \to 2, 2 \leftarrow 5)$.

Given the directions of all directed paths, determine how many "connected positive triangle intersections" exist in this graph.

Input

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$) representing the number of test cases. For each test case:

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

The second line contains a string $s_1$ of length $n$, where $s_{1i} \in \{0, 1\}$. If $s_{1i} = 0$, the direction of the left-diagonal path consisting of $i$ roads is from top-right to bottom-left; otherwise, it is the opposite.

The third line contains a string $s_2$ of length $n$, where $s_{2i} \in \{0, 1\}$. If $s_{2i} = 0$, the direction of the horizontal path consisting of $i$ roads is from left to right; otherwise, it is the opposite.

The fourth line contains a string $s_3$ of length $n$, where $s_{3i} \in \{0, 1\}$. If $s_{3i} = 0$, the direction of the right-diagonal path consisting of $i$ roads is from bottom-right to top-left; otherwise, it is the opposite.

The sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer representing the number of "connected positive triangle intersections".

Examples

Input 1

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

Output 1

1
0
4

Input 2

1
4
0011
1100
0011

Output 2

6

Note

In Example 1, the graph for the first test case:

In Example 1, the graph for the second test case:

In Example 1, the "connected positive triangle intersections" for the third test case are:

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