An array $b$ of $m$ integers is called good if, when it is sorted, $b_{\left\lfloor \frac{m + 1}{2} \right\rfloor} = b_{\left\lceil \frac{m + 1}{2} \right\rceil}$. In other words, $b$ is good if both of its medians are equal. In particular, $\left\lfloor \frac{m + 1}{2} \right\rfloor = \left\lceil \frac{m + 1}{2} \right\rceil$ when $m$ is odd, so $b$ is guaranteed to be good if it has an odd length.

You are given an array $a$ of $n$ integers. Calculate the number of good subarrays$^{\text{∗}}$ in $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le \color{red}{\textbf{10}}$) — the given array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer representing the number of good subarrays in $a$.

见题面 Input 部分

见题面 Output 部分

In the first case, every subarray is good since all its elements are equal to $1$.

In the second case, an example of a good subarray is $b = [10, 2, 3, 3]$. When it is sorted, $b = [2, 3, 3, 10]$, so $b_{\left\lfloor \frac{4 + 1}{2} \right\rfloor} = b_{\left\lceil \frac{4 + 1}{2} \right\rceil} = b_2 = b_3 = 3$. Another example would be $b = [1, 10, 2]$. On the other hand, $b = [1, 10]$ is not good as its two medians are $1$ and $10$, which are not equal.