404680: GYM101608 D Test Cases

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.

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, a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶), the values of the array.

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

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

1
7
9 1 1 2 1 9 9

12