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. Sample Input 3 6 121312 4 2424 9 10 2 2 10 3 4 5 4 3 Sample Output 2 1 2