You are given an array of size $N$ containing the integers $1, 2 \ldots N$ in some order.

A move consists of swapping the integers $k$ and $k+1$ for some $1 \le k \lt N$. In other words, you may swap any pair of integers that has a difference of one.

Find the minimum number of moves required to sort the given array in ascending order.

Input

The first line contains $T$ ($1 \le T \le 1000$), the number of test cases.

Each test case contains $N$ ($2 \le N \le 10^5$) followed by $N$ distinct integers ($1 \le x_i \le N$).

The sum of $N$ over all test cases will not exceed $10^5$.

Output

For each test case, output the number of moves required to sort the array.

Example

Input:
5
2 1 2
2 2 1
3 3 2 1
4 4 2 3 1
6 2 1 4 3 6 5

Output:
0
1
3
5
3

Note

Below is one optimal sequence of moves that sorts [4,2,3,1].

• Swap 1 and 2: [4,2,3,1] → [4,1,3,2].
• Swap 2 and 3: [4,1,3,2] → [4,1,2,3].
• Swap 3 and 4: [4,1,2,3] → [3,1,2,4].
• Swap 2 and 3: [3,1,2,4] → [2,1,3,4].
• Swap 1 and 2: [2,1,3,4] → [1,2,3,4].