当前没有测试数据。

题目描述

Summer vacation is coming and Mark has returned home from his university having successfully survived the exam week. Today, he is very bored. So his friend Alice challenges him to play a game with stones which is invented by her. Alice gives Mark $\ N$ piles of stones numbered from $\ 1$ to $\ N$, and there are aia_iai​ stones in the $\ i$-th pile. The rules of the game are simple: Mark will try to remove all stones. In each move, Mark chooses two different non-empty piles and removes one stone from each of those two piles. Mark can perform any number of moves. If all the piles are empty after some number of moves, Mark wins the game. If he can't make a valid move but not all piles are empty, he loses the game. Obviously, if the total number of stones is odd, then Mark is not able to win the game. So there is an additional rule: if initially, the total number of stones is odd, then Mark removes a single stone from the pile with the fewest stones before starting the game. If there are multiple piles with the smallest number of stones, Mark chooses one among them to remove a stone.

Mark found the optimal strategy for Alice's game very quickly and gets bored again. Also, he noticed that for some configuration of stones there is no way to win. So he challenges you to solve this problem: count the number of integer pairs $(l,r) \ (1 \le l < r \le N)$ such that it is possible for Mark to win the game if the game is played using only the piles numbered from $\ l$ to $\ r$.

输入格式

The input contains multiple cases. The first line of the input contains a single positive integer $\ T$, the number of cases. The first line of each case contains a single integer $N \ (2 \le N \le 300000)$, the number of piles. The following line contains $\ N$ space-separated integers, where the $\ i$-th integer denotes $a_i \ (1 \le a_i \le 10^9)$, the number of stones in the $\ i$-th pile. It is guaranteed that the sum of $\ N$ over all cases does not exceed $\ 1000000$.

输出格式

For each case, print a single integer on a single line, the number of pairs satisfying the required property.

样例

样例输入 1

2
3
1 1 1
4
1 2 3 4

样例输出 1

3
3