Problem Description

Given an integer array $a[1..n]$.

Count how many subsegment $[L, R]$ satisfying $R - L + 1 \geq 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 \le 15)$. Then $T$ test cases follow.

For each test case, input two lines.

For the first line, there is only one integer $n$ $(1 \leq n \leq 10^6)$.

The second line contains $n$ integers describing the array $a[1..n]$, while the restriction $0 \leq a_i \leq 10^6$ is guaranteed.

$\sum n<=6*10^6$

Output

For each test case, output a integer per line, denoting the answer of the problem.

1
10
3303 70463 3303 3303 3303 70463 3303 3303 70463 70463

47