AT_1_ttpc2024_1_k.Sum is One

给定一个由 $0$ 和 $1$ 组成的长度为 $N$ 的数列 $A = (A_1, A_2, \dots, A_N)$。定义一个包含 $\frac{N (N - 1)}{2}$ 个顶点的简单无向图 $G = (V, E)$ 如下：

• 对于满足 $1 \leq i < j \leq N$ 的任意整数对 $(i, j)$，$(i, j) \in V$。我们将这个顶点称为顶点 $(i, j)$。
• 对于满足 $1 \leq i < j < k \leq N$ 且 $A_i + A_j + A_k = 1$ 的任意整数三元组 $(i, j, k)$，存在一条连接顶点 $(i, j)$ 和顶点 $(j, k)$ 的边。
• 除此之外的顶点对之间没有边。

请计算图 $G$ 的连通分量个数。

共有 $T$ 个测试用例，对于每个测试用例，请分别求解答案。

输入从标准输入以以下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

其中，$\text{case}_i$ 表示第 $i$ 个测试用例。每个测试用例的格式如下：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

对于每个测试用例，输出答案。

约束

• 所有输入均为整数
• $1 \leq T \leq 10^5$
• $3 \leq N \leq 10^6$
• $A_i$ 为 $0$ 或 $1$ ($1 \leq i \leq N$)
• 单个输入中所有测试用例的 $N$ 的总和不超过 $10^6$

部分分

如果在满足以下约束的数据集上正确解答，则可以获得 $30$ 分：

• $1 \leq T \leq 1000$
• $3 \leq N \leq 5000$
• 单个输入中所有测试用例的 $N$ 的总和不超过 $5000$

样例解释 1

对于第一个测试用例，连通分量如下：

• $\lbrace (1,2), (2,3), (2,4), (2,5), (3,4), (4,5) \rbrace$
• $\lbrace (1,3), (3,5) \rbrace$
• $\lbrace (1,4) \rbrace$
• $\lbrace (1,5) \rbrace$

对于第二个测试用例，图中没有边，因此连通分量的个数为 $10$。