对于一个长度为 $m$ 的非负整数序列 $a_1,\ldots,a_m$，考虑 $m$ 行的棋盘，其中第 $i$ 行有 $a_i$ 列。若存在一种用 $1\times 2$ 和 $2\times 1$ 的多米诺骨牌覆盖整个棋盘的方式，则称序列 $a$ 是好的。

给出一个长度为 $n$ 的非负整数序列 $b_1,\ldots,b_n$，求有多少个 $(l,r)$ 满足 $1\le l\le r\le n$ 且 $b_l,\ldots,b_r$ 可以被删空。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来对于每组数据，输入两行：

第一行一个正整数 $n$。

第二行 $n$ 个非负整数 $b_1,\ldots,b_n$。

输出格式

对于每组数据，输出一行一个非负整数，表示答案。

样例

样例 1 输入

9
5
5 6 6 5 3
9
3 7 1 8 4 4 0 6 9
3
3 1 0
3
3 0 1
3
2 0 2
1
0
10
4 7 6 6 7 6 1 2 5 5
6
5 5 5 4 3 3
6
6 4 4 6 4 1

样例 1 输出

7
22
3
1
6
1
12
7
15

样例 1 说明

对于第一组数据，$b=[5,6,6,5,3]$，合法的 $(l,r)$ 有：$(2,2)$，$(3,3)$，$(2,3)$，$(4,5)$，$(3,5)$，$(1,4)$，$(2,5)$。

样例 2

见下发文件。

数据范围

对于所有数据，满足 $1\le T\le 100$，$1\le n\le 5\times 10^5$，$\sum n\le 10^6$，$0\le b_i\le 10^9$。

• subtask 1(5%)：$n\le 10$。
• subtask 2(20%)：$n\le 100$，$\sum n\le 5\times 10^3$。
• subtask 3(20%)：$\sum n\le 5\times 10^3$。
• subtask 4(20%)：$\sum n\le 10^5$。
• subtask 5(35%)：无特殊限制。