F. Bamboozle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For any integer $$$x$$$, define $$$f(x)$$$ as follows: $$$$$$ f(x) = (x - 1) \oplus x \oplus (x + 1) $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operator.

We call an array $$$[b_1, b_2, \dots, b_m]$$$ good if it satisfies the following condition: $$$$$$ f(b_1 + b_2 + \dots + b_m) = f(b_1) + f(b_2) + \dots + f(b_m) $$$$$$

You are given an array $$$a$$$ of length $$$n$$$. Determine the number of good subarrays.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,a_3,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.

Output

For each testcase, print the number of good subarrays.

Example
Input
4
3
1 2 3
5
5 3 6 2 1
5
8 8 3 7 2
4
69 10 54 27
Output
3
6
6
4
Note

In the first test case, there are $$$3$$$ good subarrays $$$[a_1]$$$, $$$[a_2]$$$, and $$$[a_3]$$$.