E. Musical Fragments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Martín has been digitizing his music collection for weeks. He has converted old records and recordings into a long list of numbered tracks, each labeled with a number indicating its musical style. Some tracks share a style; others are completely different. Martín boasts of having "a little bit of everything," although he suspects that he repeats more than he would like to admit.

While organizing the collection, he decides to analyze consecutive fragments of the list. A fragment of a list of $$$n$$$ elements is determined by two positions $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, and includes all tracks from the $$$l$$$-th to the $$$r$$$-th, both inclusive. For each fragment, Martín counts how many distinct styles appear in it.

He is particularly interested in those fragments that contain an odd number of different styles.

Given the sequence of styles of each collection, determine how many fragments satisfy this property.

Input

The first line contains an integer $$$T$$$, the number of test cases to process.

The first line of each case contains an integer $$$n$$$, the number of tracks in the collection.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the style of the $$$i$$$-th track.

Output

For each case, you must print a single line with an integer: the number of fragments whose number of distinct styles is odd.

Example
Input
2
3
1 2 3
5
1 1 1 1000000000 1
Output
4
8
Note
  • $$$1 \le T \le 10^5$$$
  • $$$1 \le n \le 10^5$$$
  • The sum of $$$n$$$ across all cases will be at most $$$10^5$$$.
  • $$$1 \le a_i \le 10^9$$$