Minimum Adjacent Swaps to Sort Array

Problem Description:

You are given several test cases. In each test case, you are provided with an array of integers. Your task is to determine the minimum number of adjacent swaps required to sort the array in non-decreasing order. This is equivalent to counting the number of inversions in the array, where an inversion is defined as a pair of indices (i < j) such that (a_i > a_j).

For example, in the array [2, 3, 4, 1], there are three inversions, so you would need 3 adjacent swaps to sort it.

The input is read from STDIN and the result for each test case should be printed to STDOUT.

inputFormat

Input Format:

The first line contains an integer (T), the number of test cases. Each test case consists of two lines. The first line contains an integer (N), the size of the array. The second line contains (N) space-separated integers representing the elements of the array.

Example:
2
5
5 4 3 2 1
4
2 3 4 1

outputFormat

Output Format:

For each test case, output a single line containing the minimum number of adjacent swaps needed to sort the array.## sample

2
5
5 4 3 2 1
4
2 3 4 1

10
3