C. Calculation of Intervals
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ of $$$n$$$ integers. You need to answer how many intervals there are where at least one number occurs an odd number of times in this interval.

An interval can be obtained by deleting zero or more integers from the beginning and zero or more integers from the end of the array.

Input

Each test consists of several test cases. The first line contains a single integer $$$t(1\leq{t}\leq{10^6})$$$—the number of test cases. Then follows the description of the test cases.

The first line of each test case contains an integer $$$n(1\leq{n}\leq{10^6})$$$ — the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n(1\leq{a_i}\leq{10^6})$$$ — the array $$$a$$$ itself.

It is guaranteed that the sum of the value of $$$n$$$ for all test cases does not exceed $$$10^6$$$.

Output

For each test, output a single integer, the number of eligible intervals.

Example
Input
2
4
1 1 1 1
5
1 2 3 2 3
Output
6
14