Given a list of integers, find out how many shifts it will take to sort the list using insertion sort algorithm.
InputFirst line of input will contain a positive integer T = number of test cases. Each test case will contain 2 lines. First line will contain a positive integer N = number of elements in a list. Next line will contain N space separated integers. There will be no duplicate in a list.
OutputFor each test case, print on a single line the total number of shifts performed while sorting the list using insertion sort algorithm. A shift is any change in position of an element in the list while performing insertion sort.
Sample Input3 5 2 4 1 3 5 10 10 9 8 7 6 5 4 3 2 1 5 1 2 3 4 5Sample Output
5 54 0Explanation
2,4,1,3,5 => 2,4,1,3,5 (0 shifts) => 1,2,4,3,5 (3 shifts - any change in position is shift) => 1,2,3,4,5 (2 shifts) - total 5 shifts