Wesley Crusher is the teaching assistant for Introduction to Algorithms. During his rst class, the cadets were asked to come up with their own sorting algorithms. Monty came up with the following code: \textbf{while (!sorted(a)) \{} \textbf{int i = random(n);} \textbf{int j = random(n);} \textbf{if (a\[min(i,j)\] > a\[max(i,j)\])} \textbf{swap(a\[i\], a\[j\]);} \textbf{\}} Carlos, inspired, came up with the following code: \textbf{while (!sorted(a)) \{} \textbf{int i = random(n-1);} \textbf{int j = i + 1;} \textbf{if (a\[i\] > a\[j\])} \textbf{swap(a\[i\], a\[j\]) ;} \textbf{\}} Wesley needs to determine which algorithm is better. For a given input array of up to \textbf{8} values, calculate and print the expected number of iterations for each algorithm. That is, on average, how many iterations should each algorithm take for the given input? \InputFile The first line contains \textbf{T}, the number of test cases: \textbf{2} ≤ \textbf{T} ≤ \textbf{100}. Each test case is given on a single line. The first value is \textbf{N}, the number of array elements; \textbf{2} ≤ \textbf{N} ≤ \textbf{8}. This is followed on the same line by \textbf{N} integer array elements. The array elements will have values between \textbf{0} and \textbf{100} inclusive. The array elements may not be distinct. \OutputFile For each test case, print out the expected number of iterations for Monty's algorithm and for Carlos's algorithm, as shown in the sample output section. There should be exactly one space between words and no spaces at the start of each line or at the end of each line. There should be exactly six digits after the decimal point. Rounding should be to nearest representable value.