Ke'le has a sequence of positive integers $A_i$ of length $n$, where identical integers represent the same color.

Ke'le feels that this sequence is too long, so she decides to choose some colors and remove all occurrences of those colors from the sequence.

Removing color $i$ is defined as removing all positions $j$ such that $A_j = i$ from the sequence.

However, sometimes after removal, the sequence splits into several segments. Ke'le does not like this, so she wants to know how many ways to choose a set of colors to remove such that the remaining sequence is non-empty and contiguous.

For example, for the color sequence $[1, 2, 3, 4, 5]$, removing color $3$ results in the sequence becoming $[1, 2]$ and $[4, 5]$, which consists of two segments and does not satisfy the condition.

On the other hand, removing color $1$ results in the sequence becoming $[2, 3, 4, 5]$, which satisfies the condition.

Two schemes are different if and only if there exists at least one color $i$ that is removed in one scheme but not the other.

Input

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

For each test case, the first line contains an integer $n$, representing the length of the sequence.

The second line contains $n$ integers describing the color sequence.

Output

For each test case, output an integer representing the answer.

Examples

Input 1

1
5
1 3 2 4 3

Output 1

6

Note 1

The color removal schemes that satisfy the condition are $[1], [1, 3], [1, 2, 3], [1, 3, 4], [2, 3, 4], \varnothing$.

Subtasks

For $20\%$ of the data, it is guaranteed that $1 \leq \sum n \leq 20$.

For $40\%$ of the data, it is guaranteed that $1 \leq \sum n \leq 500$.

For $60\%$ of the data, it is guaranteed that $1 \leq \sum n \leq 10^4$.

For $100\%$ of the data, it is guaranteed that $1 \leq T, \sum n \leq 3 \times 10^5$ and $1 \leq A_i \leq n$.