Inwersją w ciągu liczb A[1..n] nazywamy każdą taką parę liczb A[i], A[j], że i<j oraz A[i]>A[j].
Dla danego ciągu liczb wyznacz liczbę występujących w nim inwersji.
UWAGA! Program musi działać szybko, tzn. czas jego działania nie może być większy niż O(nlgn).

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita d (1 <= d <= 100), która oznacza liczbę zestawów danych.
Każdy zestaw składa się z dwóch linii. W pierwszej z nich znajduje się liczba n (1<=n<=30000), oznaczająca liczbę elementów ciągu.
W drugiej linii znajduje się n liczb całkowitych z przedziału od -1000 do 1000, które oznaczają kolejne elementy ciągu.

Wyjście

Na wyjściu należy dla każdego zestawu danych wypisać liczbę inwersji w zadanym ciągu.

Przykład

Wejście:
2
5
1 2 3 1 5
4
4 3 2 1

Wyjście:
2
6