Count Bubble Sort Swaps

Given an array of integers, your task is to determine the number of swaps required by the bubble sort algorithm to sort the array in ascending order.

In bubble sort, the algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Given multiple test cases, output the number of swaps performed for each test case.

Note: The number of swaps can be mathematically represented as $$S = \sum_{i=0}^{n-1}\sum_{j=0}^{n-i-2} \mathbb{1}{{a[j] > a[j+1]}}$$ where (\mathbb{1}{{a[j] > a[j+1]}}) is an indicator function that is 1 if (a[j] > a[j+1]) and 0 otherwise.

inputFormat

The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (n), the size of the array. The second line contains (n) space-separated integers representing the array.

outputFormat

For each test case, output a single integer representing the number of swaps performed by the bubble sort algorithm. Each result should be printed on a new line.## sample

1
1
1

0