题目描述

A 镇上有 $\frac{(n+1)(n+2)}{2}$ 个路口，这些路口由 $3n$ 条路径连接，构成了一个边长有 $n$ 条道路的正三角形。$n=3$ 的情况如下图所示：

:::align{center} :::

这 $3n$ 条路径可以分成左斜，水平和右斜三个方位，每个方位各包含 $n$ 条路径。每个方位的第 $i$ 条路径由 $i$ 条道路组成。

例如在 $n=3$ 时：

• 左斜的路径从道路数量由少至多分别为 $(6\leftrightarrow9)$, $(3\leftrightarrow5\leftrightarrow8)$, $(1\leftrightarrow2\leftrightarrow4\leftrightarrow7)$。
• 水平的路径从道路数量由少至多分别为 $(2\leftrightarrow3)$, $(4\leftrightarrow5\leftrightarrow6)$, $(7\leftrightarrow8\leftrightarrow9\leftrightarrow10)$。
• 右斜的路径从道路数量由少至多分别为 $(4\leftrightarrow8)$, $(2\leftrightarrow5\leftrightarrow9)$, $(1\leftrightarrow3\leftrightarrow6\leftrightarrow10)$。

我们称三个不同的路口 $(u,v,w)$ 是一个长度为正整数 $l$ 的“正三角形”路口，当且仅当我们可以在任意重排 $u,v,w$ 三个点的顺序后满足：

• 从 $u$ 出发经过 $l$ 条左斜的道路到达 $v$；
• 从 $v$ 出发经过 $l$ 条水平的道路到达 $w$；
• 从 $w$ 出发经过 $l$ 条右斜的道路到达 $u$。

或者：

• 从 $u$ 出发经过 $l$ 条右斜的道路到达 $v$；
• 从 $v$ 出发经过 $l$ 条水平的道路到达 $w$；
• 从 $w$ 出发经过 $l$ 条左斜的道路到达 $u$。

例如上图中 $(2,4,5)$，$(2,3,5)$ 是“正三角形”路口，而 $(2,3,4)$ 不是。

A 镇为了处理交通过于拥堵，因此决定给每条道路定向。在定向之后，每条道路存在唯一固定的方向，且每条路径上的道路方向相同。

如下图是一种可能的定向情况（对应着样例 $1$ 的第三组测试数据）：

:::align{center} :::

称图中的三个不同的路口 $(u,v,w)$ 为“连通的正三角形”路口，当且仅当它们在图中构成了一个长度为正整数 $l$ 的“正三角形”路口，且它们可以通过构成该“正三角形”路口的 $3l$ 条道路相互到达。例如在上图中：

• $(2, 4, 5)$ 是一个“连通的正三角形”路口。因为它们不仅是“正三角形”路口，且只通过该“正三角形”路口的道路 $(2 \rightarrow 4,4 \rightarrow 5, 5 \rightarrow 2)$ 相互到达。
• $(2, 3, 4)$ 不是一个“连通的正三角形”路口。因为它们不是一个“正三角形”路口。
• $(2, 3, 5)$ 不是一个“连通的正三角形”路口。因为它们虽然是“正三角形”路口，但不能通过该“正三角形”路口的道路$(5 \rightarrow 3, 3 \rightarrow 2, 2 \leftarrow 5)$ 相互到达。

现在告知所有有向路径的方向告诉你，询问这个图中到底有多少个“连通正三角形路口”。

输入格式

本题包含多组测试数据。输入第一行输入一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示正三角形的长度。

第二行包含一个长度为 $n$ 的字符串 $s1$，其中 $s1_i \in \{\text{0, 1}\}$，其中若 $s1_i=\text{0}$ 则表示由 $i$ 条道路构成的左斜路径的方向是右上向左下，反之亦然。

第三行包含一个长度为 $n$ 的字符串 $s2$，其中 $s2_i \in \{\text{0, 1}\}$，其中若 $s2_i=\text{0}$ 则表示由 $i$ 条道路构成的水平路径的方向是左向右，反之亦然。

第四行包含一个长度为 $n$ 的字符串 $s3$，其中 $s3_i \in \{\text{0, 1}\}$，其中若 $s3_i=\text{0}$ 则表示由 $i$ 条道路构成的右斜路径的方向是右下向左上，反之亦然。

保证所有数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组数据，输出一个整数，表示“连通正三角形路口”的数量。

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

1
0
4

1
4
0011
1100
0011

6

提示

样例一中，第一组测试数据的图形：

:::align{center} :::

样例一中，第二组测试数据的图形：

:::align{center} :::

样例一中，第三组测试数据的“连通正三角形路口”有：

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