GoroSort

Goro에게는 4개의 팔이 있다. Goro는 매우 강하다. Goro에게 함부로 덤벼서는 안 된다. Goro는 서로 다른 정수 N개로 이루어진 배열을 정렬해야 한다. 알고리즘은 Goro의 강점이 아니지만, 힘은 Goro의 강점이다. Goro의 계획은 두 손의 손가락으로 배열의 여러 원소를 눌러 고정하고, 세 번째와 네 번째 주먹으로 탁자를 가능한 한 세게 내리치는 것이다. 그러면 고정되지 않은 배열의 원소들이 공중으로 날아올라 무작위로 섞인 뒤, 배열의 빈 위치로 다시 떨어진다.

Goro는 배열을 가능한 한 빨리 정렬하고 싶어 한다. 탁자를 칠 때마다 그 전에 배열의 어느 원소를 눌러 고정할지 현명하게 선택한다면, 주어진 배열을 정렬하는 데 평균적으로 몇 번을 쳐야 하는가? Goro가 배열을 눌러 고정하는 데 사용하는 두 손에는 손가락이 무한히 많다.

더 정확히 말하면, Goro는 탁자를 칠 때마다 그 전에 배열 원소의 임의의 부분집합을 제자리에 고정할 수 있다. 이전에 탁자를 친 결과에 따라 다른 부분집합을 선택할 수도 있다. 탁자를 한 번 칠 때마다 고정되지 않은 원소들은 균등한 확률로 무작위 순열을 이룬다. 각 순열이 나올 확률은 모두 같다.

제한

1 ≤ T ≤ 100; 각 테스트 케이스의 두 번째 줄에는 가장 작은 양의 정수 N개의 순열이 주어진다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10; 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 1000; 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 수 N이 주어진다. 두 번째 줄에는 배열의 N개 원소가 초기 순서대로 나열된다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며(1부터 시작), y는 최적의 고정 전략을 따를 때 탁자를 치는 연산 횟수의 기댓값이다. 절대 오차 또는 상대 오차가 최대 10^{-6}인 답은 정답으로 인정된다.

설명

테스트 케이스 #3에서 가능한 전략 중 하나는 먼저 가장 왼쪽의 두 원소를 눌러 고정하는 것이다. 원소 3와 4는 자유롭게 움직일 수 있다. 탁자를 한 번 치면 이 원소들은 1/2의 확률로 올바른 순서 $[3, 4]$로 놓이고, 1/2의 확률로 잘못된 순서 $[4, 3]$로 놓인다. 따라서 이 원소들을 올바른 순서로 배열하는 데 평균적으로 2번을 쳐야 한다. 그런 다음 Goro는 원소 3와 4를 눌러 고정하고, 1와 2가 올바른 순서로 놓일 때까지 탁자를 칠 수 있으며, 여기에는 평균적으로 다시 2번이 필요하다. 따라서 총횟수는 2 + 2 = 4번이다.