You are given an array $A$ having $N$ integers. Find the number of triplets $(i, j, k)$ such that 

• $1 \le i \lt j \lt k \le N$.
• The integer $A_j$ is equal to the median of the integers $A_i,A_j,A_k$.

The median of three integers is the middle element after sorting the three integers. For example, the median of $(5, 1, 3)$ is $3$, $(2, 4, 4)$ is $4$.

Input format

• The first line of input contains an integer $T$ denoting the number of test cases. The description of each test case is as follows:
• The first line of each test case contains an integers $N$.
• The second line of each test case contains $N$ integers $A_1, A_2,\dots, A_N$.

Output format

For each test case, print the number of triplets that satisfies the given conditions in a separate line.

Constraints

$1\le T \le 10^5 \\ 1 \leq N \le 10^5\\ 1\le A_i \le N\\ \text{Sum of $N$ over all test cases does not exceed }3\cdot 10^5.$