在 Berland，主要货币是 burle，人们通常使用面值为 1 或 2 burle 的硬币进行购物。

对于一个硬币的多重集 $S$，我们将其便利度定义为最大的非负整数 $x$，使得对于每个整数 $i \in [0, x]$，都可以从 $S$ 中选择若干个硬币（可以全部选择，也可以不选），使它们的总面值恰好为 $i$ burle。

给你一个数组 $a_1, a_2, \dots, a_n$，其中每个元素要么是 1 要么是 2。你需要计算 $\sum_{l=1}^{n} \sum_{r=l}^{n} F(l, r)$，其中 $F(l, r)$ 是由面值为 $a_l, a_{l+1}, \dots, a_r$ 的硬币组成的多重集的便利度。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$ ($2 \le n \le 3 \cdot 10^5$)。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2$)。

输入的附加限制：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— $\sum_{l=1}^{n} \sum_{r=l}^{n} F(l, r)$ 的值。

样例

输入样例 1

4
3
1 2 1
2
2 2
4
2 1 2 1
7
1 2 2 1 1 2 1

输出样例 1

12
0
26
113