D. Test Cases
time limit per test
2 seconds
memory limit per test
256 megabytes
input
cases.in
output
standard output

You want to prepare test cases for a problem with the following description:

"Given an array of n positive integers, and a number of queries. Each query will ask about a range [l, r] (1 ≤ l ≤ r ≤ n), where each of the values between index l and index r (both inclusive) occurs an even number of times except one value. The answer to each query is the value that occurs an odd number of times in the given range."

You have generated an array of n positive integers, you need to know the number of valid queries you can ask on this array. A query is valid if it has an answer, and that answer is unique.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 64), the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 5000), the size of the array.

The next line contains n space-separated integers, a1, a2, ..., an (1 ≤ ai ≤ 106), the values of the array.

The total sum of n overall test cases doesn't exceed 72000.

Output

For each test case, print a single line with the number of valid queries you can ask.

Example
Input
1
7
9 1 1 2 1 9 9
Output
12