Minimum Swaps Using Bubble Sort

In this problem, you are given an unsorted array of integers. Your task is to determine the number of swaps performed by the bubble sort algorithm to sort the array.

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process is repeated until the array becomes sorted.

The total number of swaps can be described by the formula: $$\text{Swaps} = \sum_{i=0}^{n-1} \sum_{j=0}^{n-i-2} \mathbf{1}(a_j > a_{j+1})$$, where $$\mathbf{1}(condition)$$ is 1 if the condition is true and 0 otherwise.

inputFormat

The input begins with a single integer T, representing the number of test cases. Each test case starts with an integer n (the number of elements in the array), followed by n space-separated integers representing the array elements.

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

outputFormat

For each test case, output a single integer that denotes the number of swaps performed by the bubble sort algorithm to sort the given array. Each output should be written on a new line.## sample

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

6
2
0