## SWAPDIFF1 - Difference One Swaps

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 5Output: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].

Added by: | traxex |

Date: | 2018-04-19 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own problem |