Crusher's Code

Wesley Crusher is the teaching assistant for Introduction to Algorithms. In the first class the cadets were asked to come up with a sorting algorithm of their own. Monty came up with this code.

while (!sorted(a)) {
    int i = random(n) ;
    int j = random(n) ;
    if (a[min(i,j)] > a[max(i,j)])
        swap(a[i], a[j]) ;
}

Carlos, inspired by it, came up with this code.

while (!sorted(a)) {
    int i = random(n-1) ;
    int j = i + 1 ;
    if (a[i] > a[j])
        swap(a[i], a[j]) ;
}

The array a holds $N$ elements numbered 0 through $N-1$, and the n in the code is that $N$. Every call to random(k) independently picks one integer from 0 to $k-1$, all with the same probability. The number of iterations is the number of times the body of the while statement runs. An iteration that only compares two values without swapping them still counts. An array that is already sorted never enters the body, so its number of iterations is 0.

Wesley has to decide which algorithm is better. Given an array of at most 8 values, compute the expected number of iterations each algorithm runs before that array is sorted.

The first line contains the number of test cases $T$ ($2 \le T \le 100$).

Each test case is given on a single line. The first value on the line is the number of array elements $N$ ($2 \le N \le 8$), followed by the $N$ elements of the array separated by spaces. Every element is an integer from 0 to 100, and the same value may appear more than once.

For each test case, print the expected number of iterations for Monty's algorithm and for Carlos's algorithm on one line, in the form Monty <Monty's expectation> Carlos <Carlos's expectation>.

Print both expectations with exactly six digits after the decimal point, rounding at the seventh digit. Put exactly one space between words, and no space at the start or the end of a line. No answer comes within $10^{-9}$ of a rounding boundary, so the digits are the same whichever way a boundary would be resolved.