You are given a permutation$^{\text{∗}}$ $p$ of length $n$.

For each index $i$, you may move in one step to:

• any index $j \lt i$, or
• the first index $j \gt i$ such that $p_j \gt p_i$ (if such an index exists),

In other words:

• You can always move to any position on the left.
• On the right, you can move only to the nearest position whose value is strictly greater than the current one.

For every pair of indices $(i,j)$, let $f(i,j)$ be the minimum number of steps needed to move from $i$ to $j$. Note that if we cannot reach $j$ from $i$, then $f(i,j)=0$.

Your task is to compute:

$$\sum_{1 \le i,j \le n} f(i,j).$$

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

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 \leq n \leq 10^6$) — the length of $p$.

The second line of each test case contains $n$ distinct integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$) — the elements of $p$.

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

Output

For each test case, print a single integer — the value of $\sum\limits_{1 \le i,j \le n} f(i,j)$.

Note

In the first test case, $f(1, 2) + f(2, 1) = 1 + 1 = 2$.

In the second test case, $f(1, 2) + f(2, 1) = 0 + 1 = 1$.

In the third test case, $f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 0 + 1 + 0 + 1 + 1 = 4$.

In the fourth test case, $f(1, 2) + f(1, 3) + f(2, 1) + f(2, 3) + f(3, 1) + f(3, 2) = 1 + 2 + 1 + 1 + 1 + 1 = 7$.