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.\)