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