I - Interesting 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.

Sample Input	Sample Output
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