Champion Sort (Large)

Someone here sorts numbers in a very unusual way.

And his name is John Cena!!!!

John Cena is no algorithms expert, so he sorts numbers his own way. The array he wants to sort holds each of the natural numbers from $1$ to $N$ exactly once. He first picks a few elements of the array and shouts "You can't see me". Then he hits every picked element with a Five Knuckle Shuffle at the same time. The picked elements take heavy damage and their order is shuffled at random. Every arrangement of the picked elements comes up with the same probability.

Five Knuckle Shuffles thrown at the same time count as one, no matter how many elements were picked. John Cena repeats this until the array is sorted in increasing order, and each time he looks at the result so far before deciding which elements to pick next. John Cena plays optimally and makes the expected number of Five Knuckle Shuffles as small as possible. What is that expected value?

The first line contains the number of test cases $T$. Each test case consists of two lines. The first line contains the array length $N$, and the second line contains the $N$ elements of the array in order.

$1 \le T \le 100$ and $1 \le N \le 1000$. The array holds each of the natural numbers from $1$ to $N$ exactly once.

For each test case, print the test case number $x$ and the minimum expected value $y$ on one line in the form Case #x: y. Print $y$ rounded to six digits after the decimal point.

For the array $[2, 1]$, John Cena picks both elements and throws a Five Knuckle Shuffle. The array is sorted with probability $1/2$ and stays the same with probability $1/2$, so the expected value is $2$.

For the array $[1, 3, 2]$, he picks $3$ and $2$ and throws a Five Knuckle Shuffle. For the same reason as above, the expected value is $2$.

For the array $[2, 1, 4, 3]$, he first picks $2$ and $1$. The expected value up to that point is $2$. He then picks $4$ and $3$, and the total expected value becomes $4$.