## #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 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