For a sequence of non-negative integers $a_1, \ldots, a_m$ of length $m$, consider a board with $m$ rows, where the $i$-th row has $a_i$ columns. A sequence $a$ is called "good" if there exists a way to tile the entire board using $1 \times 2$ and $2 \times 1$ dominoes.

Given a sequence of non-negative integers $b_1, \ldots, b_n$ of length $n$, find the number of pairs $(l, r)$ such that $1 \le l \le r \le n$ and the subsequence $b_l, \ldots, b_r$ is good.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the input consists of two lines:

The first line contains a positive integer $n$.

The second line contains $n$ non-negative integers $b_1, \ldots, b_n$.

Output

For each test case, output a single line containing a non-negative integer representing the answer.

Examples

Input 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

Output 1

7
22
3
1
6
1
12
7
15

Note 1

For the first test case, $b=[5,6,6,5,3]$, the valid pairs $(l, r)$ are: $(2,2)$, $(3,3)$, $(2,3)$, $(4,5)$, $(3,5)$, $(1,4)$, $(2,5)$.

Example 2

See the provided files.

Constraints

For all test cases, $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%): No additional constraints.