#215566. [CCPC 2025 哈尔滨站] 连通的正三角形

A 镇上有 个路口，这些路口由 条路径连接，构成了一个边长有 条道路的正三角形。 的情况如下图所示：

:::align{center} :::

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

例如在 时：

• 左斜的路径从道路数量由少至多分别为 , , 。
• 水平的路径从道路数量由少至多分别为 , , 。
• 右斜的路径从道路数量由少至多分别为 , , 。

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

• 从 出发经过 条左斜的道路到达 ；
• 从 出发经过 条水平的道路到达 ；
• 从 出发经过 条右斜的道路到达 。

或者：

• 从 出发经过 条右斜的道路到达 ；
• 从 出发经过 条水平的道路到达 ；
• 从 出发经过 条左斜的道路到达 。

例如上图中 ， 是“正三角形”路口，而 不是。

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

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

:::align{center} :::

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

• 是一个“连通的正三角形”路口。因为它们不仅是“正三角形”路口，且只通过该“正三角形”路口的道路 相互到达。
• 不是一个“连通的正三角形”路口。因为它们不是一个“正三角形”路口。
• 不是一个“连通的正三角形”路口。因为它们虽然是“正三角形”路口，但不能通过该“正三角形”路口的道路 相互到达。

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

本题包含多组测试数据。输入第一行输入一个整数 ()，表示测试数据组数。

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

第一行包含一个整数 ()，表示正三角形的长度。

第二行包含一个长度为 的字符串 ，其中 ，其中若 则表示由 条道路构成的左斜路径的方向是右上向左下，反之亦然。

第三行包含一个长度为 的字符串 ，其中 ，其中若 则表示由 条道路构成的水平路径的方向是左向右，反之亦然。

第四行包含一个长度为 的字符串 ，其中 ，其中若 则表示由 条道路构成的右斜路径的方向是右下向左上，反之亦然。

保证所有数据的 之和不超过 。

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

样例输入 1

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

样例输出 1

1
0
4

样例输入 2

1
4
0011
1100
0011

样例输出 2

6

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

:::align{center} :::

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

:::align{center} :::

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

• ;
• ;
• ；
• 。