#1241 Random Sort

14  7 s   128 MB  

Description

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i]and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

 

Input

 

The first line contains the number of test cases T (T ≤ 200).

For each test case, space-separated two integers n - number of elements in permutation - and n integers as permutation given on the first line.

 

Constraints

- permutation will contain between 1 and 8 elements, inclusive.
- permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.

Output

Output the answer of each test case on a separate line. You should round the result to sixth digits after the decimal point.

 

 

 

Sample Input

Sample Output

4
3 1 3 2
4 4 3 2 1
1 1
6 2 5 1 6 3 4
1.00000
4.06667
0.00000
5.66667