챔피언 소트 (스몰)

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

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

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

존 시나는 셔플을 날릴 때마다 지금 배열 상태를 보고 다음에 고를 원소를 정한다. 그는 배열이 오름차순으로 정렬될 때까지 필요한 파이브 너클 셔플 횟수의 기댓값을 최소로 만들려고 한다. 동시에 날린 파이브 너클 셔플은 한 번으로 센다. 그 최소 기댓값을 구하라.

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

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

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

첫 번째 예제의 케이스 #1에서 존 시나는 두 원소를 모두 고른다. $1/2$의 확률로 배열이 정렬되고 $1/2$의 확률로 그대로이므로 기댓값은 2다.

케이스 #2에서는 3과 2를 고른다. 케이스 #1과 같은 이유로 기댓값은 2다.

케이스 #3에서는 2와 1을 고르고, 그 다음 4와 3을 고른다. 두 번 모두 기댓값이 2이므로 전체 기댓값은 4다.