There are $n$ people, numbered from $1$ to $n$, sitting at a round table. Person $i+1$ is sitting to the right of person $i$ (with person $1$ sitting to the right of person $n$).

You have come up with a better seating arrangement, which is given as a permutation $p_1, p_2, \dots, p_n$. More specifically, you want to change the seats of the people so that at the end person $p_{i+1}$ is sitting to the right of person $p_i$ (with person $p_1$ sitting to the right of person $p_n$). Notice that for each seating arrangement there are $n$ permutations that describe it (which can be obtained by rotations).

In order to achieve that, you can swap two people sitting at adjacent places; but there is a catch: for all $1 \le x \le n-1$ you cannot swap person $x$ and person $x+1$ (notice that you can swap person $n$ and person $1$). What is the minimum number of swaps necessary? It can be proven that any arrangement can be achieved.

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 10\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($3 \le n \le 200\,000$) — the number of people sitting at the table.

The second line contains $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \ne p_j$ for $i \ne j$) — the desired final order of the people around the table.

The sum of the values of $n$ over all test cases does not exceed $200\,000$.

For each test case, print the minimum number of swaps necessary to achieve the desired order.