챔피언 소트 (Large)

여기 아주 특이한 방법으로 정렬을 하는 사람이 있다.

그리고 그의 이름은 존 시나!!!!

알고리즘 전문가가 아닌 존 시나는 자기만의 방법으로 수를 정렬한다. 존 시나가 정렬할 배열에는 $1$부터 $N$까지의 자연수가 하나씩 들어 있다. 존 시나는 먼저 배열에서 원소를 몇 개 고른 뒤 "You can't see me"라고 외친다. 그리고 고른 원소에 동시에 파이브 너클 셔플을 날린다. 그러면 고른 원소가 큰 대미지를 입고 순서가 무작위로 섞인다. 고른 원소를 늘어놓는 방법은 모두 같은 확률로 나온다.

동시에 날린 파이브 너클 셔플은 원소를 몇 개 골랐든 한 번으로 센다. 존 시나는 배열이 오름차순으로 정렬될 때까지 이 동작을 반복하고, 매번 그때까지 나온 결과를 보고 다음에 고를 원소를 정한다. 존 시나가 최적의 전략을 써서 파이브 너클 셔플 횟수의 기댓값을 최소로 만들 때, 그 기댓값은 얼마인가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 배열의 길이 $N$이 주어지고, 둘째 줄에 배열의 원소 $N$개가 차례대로 주어진다.

$1 \le T \le 100$, $1 \le N \le 1000$이다. 배열에는 $1$부터 $N$까지의 자연수가 하나씩 들어 있다.

각 테스트 케이스마다 테스트 케이스 번호 $x$와 최소 기댓값 $y$를 Case #x: y 형식으로 한 줄에 출력한다. $y$는 반올림해서 소수점 아래 여섯째 자리까지 출력한다.

배열이 $[2, 1]$이면 존 시나는 두 원소를 모두 골라 파이브 너클 셔플을 날린다. $1/2$의 확률로 배열이 정렬되고 $1/2$의 확률로 그대로 남으므로 기댓값은 $2$다.

배열이 $[1, 3, 2]$이면 $3$과 $2$를 골라 파이브 너클 셔플을 날린다. 앞과 같은 이유로 기댓값은 $2$다.

배열이 $[2, 1, 4, 3]$이면 먼저 $2$와 $1$을 골라 파이브 너클 셔플을 날린다. 여기까지의 기댓값은 $2$다. 이어서 $4$와 $3$을 골라 파이브 너클 셔플을 날리면 전체 기댓값은 $4$다.