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

• 对于每一对满足 $1 \le i < j \le N$ 的整数 $(i, j)$，$(i, j) \in V$。该顶点称为顶点 $(i, j)$。
• 对于每一组满足 $1 \le i < j < k \le 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 \ \dots \ A_N$

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

输出格式

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

样例

输入 1

4
5
1 0 0 1 0
5
1 1 1 1 1
12
0 0 1 1 1 0 0 0 1 0 1 0
20
0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1

输出 1

4
10
13
58

说明

在第一组测试用例中，连通分量如下：

• $\{(1, 2), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)\}$
• $\{(1, 3), (3, 5)\}$
• $\{(1, 4)\}$
• $\{(1, 5)\}$

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