Count how many subsegment [L,R] satisfying R−L+1≥1 and there is a kind of integer whose number of occurrences is strictly greater than the sum of others in a[L..R].
Input
The first line contains an integer T(T≤15). Then T test cases follow.
For each test case, input two lines. For the first line, there is only one integer n(1≤n≤106).
The second line contains n integers describing the array a[1..n], while the restriction 0≤ai≤106 is guaranteed.
∑n<=6∗106
Output
For each test case, output a integer per line, denoting the answer of the problem.