#12385Interesting Sequences

For a sequence of integer numbers < x1, x2, . . . , xn >, a contiguous subsequence < xi, xi+1, . . . , xj > where i < j ≤ n, is called “interesting” if its first and last elements are equal (i.e., xi = xj ). Two interesting subsequences S1 =< xi, xi+1, . . . , xj > and S2 =< xa, xa+1, . . . , xb > 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