对于一个长度为 $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%)：无特殊限制。