Part 5 of 15 in Sorting  

How many swaps in Selection Sort ? by phantom11

Problem statement

As the problem title suggests, you need to count the number of swaps required to sort a given list of integers in ascending order using the selection sort algorithm.

Input

First line of the input contains the number of test cases T. T test cases follow. The first line of each test case contains the N, (1 ≤ N ≤ 50) the number of integers in the array. The second line contains N space separated integers. All N numbers are distinct.

Output

For each test case, print on one line, the number of swaps (minimum) to sort the given array in ascending order using selection sort.

Sample Input
2
3
4 2 5
5
10 11 8 7 1
Sample Output
1
3


To try out your code



Sign in

Sign up