404680: GYM101608 D Test Cases

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Test Casestime limit per test2 secondsmemory limit per test256 megabytesinputcases.inoutputstandard 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.

ExampleInput
1
7
9 1 1 2 1 9 9
Output
12

加入题单

上一题 下一题 算法标签: