14 7 s 128 MB

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.

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