P15564 [CCPC 2025 哈尔滨站] 连通的正三角形

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

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

样例一中，第一组测试数据的图形： :::align{center}  ::: 样例一中，第二组测试数据的图形： :::align{center}  ::: 样例一中，第三组测试数据的“连通正三角形路口”有： - $(2, 4, 5)$; - $(4, 7, 8)$; - $(5, 6, 9)$； - $(2, 7, 9)$。