#12385Interesting Sequences

For a sequence of integer numbers < x₁, x₂, . . . , x_n >, a contiguous subsequence < x_i, x_i+1, . . . , x_j > where i < j ≤ n, is called “interesting” if its first and last elements are equal (i.e., x_i = x_j). Two interesting subsequences S₁ =< x_i, x_i+1, . . . , x_j > and S₂ =< x_a, x_a+1, . . . , x_b > are called “conflict-free” if either a ≥ j or i ≥ b. For a given sequence of known size, find the maximum number of interesting subsequences which are pairwise conflict-free.

Input

The first line of input contains an integer T ≤ 100 denoting the number of test-cases. Each test-case begins with an integer 1 ≤ N ≤ 100, 000, on a separate line, denoting the size of the sequence. The following line contains N positive integers each between 1 and 100,000 (inclusive).

Output

For each test-case, output on a single line the maximum number of pairwise conflict-free interesting subsequences.

3
6
1 2 1 3 1 2
4
2 4 2 4
9
10 2 2 10 3 4 5 4 3

2
1
2