까다로운 트리오

까다로운 트리오 게임은 1라고 표시된 동일한 카드 세 장, 2라고 표시된 동일한 카드 세 장, 이런 식으로 N이라고 표시된 동일한 카드 세 장까지로 구성된 3N장의 카드 덱을 사용하여 진행한다. 카드를 섞고(가능한 모든 카드 순서가 나타날 확률이 같도록), 모든 숫자가 보이지 않게 뒷면이 위를 향하도록 탁자 위에 나누어 놓는다.

게임의 각 라운드는 다음과 같이 진행된다.

• 카드 중 하나를 골라 뒤집어서 숫자를 공개한다.

• 두 번째 카드를 골라 뒤집어서 숫자를 공개한다. 그 숫자가 첫 번째 카드에 공개된 숫자와 같지 않으면 라운드가 끝나며 세 번째 카드를 뒤집을 수 없다. 같다면 다음을 수행한다.

• 세 번째 카드를 골라 뒤집어서 숫자를 공개한다. 그 숫자가 두 번째 카드에 공개된 숫자와 같지 않으면 라운드가 끝난다. 같다면 트리오를 찾은 것이므로 카드 세 장을 모두 게임에서 제거할 수 있으며, 그 후 라운드가 끝난다.

• 라운드가 끝났을 때 남은 카드가 더 이상 없으면 게임에서 승리한다. 그렇지 않으면 다음 라운드를 시작하기 전에 공개된 카드를 모두 다시 뒤집어 숫자를 숨겨야 하지만, 기억력이 매우 뛰어나므로 게임이 끝날 때까지 그 위치를 기억할 수 있다.

이미 숫자를 알고 있는 카드도 뒤집기로 선택할 수 있다는 점에 유의한다. 또한 트리오에 속한 모든 카드의 위치를 알고 있더라도, 그 트리오를 제거하려면 같은 라운드에 카드 세 장을 모두 실제로 뒤집어야 한다.

가능한 한 빨리 승리하고 싶으므로, 게임을 끝내는 데 필요한 라운드 수의 기댓값을 최소화하는 전략을 사용한다. 그 라운드 수의 기댓값은 얼마인가?

제한

테스트 세트당 시간 제한: 20초. 메모리 제한: 1GB.

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

1 ≤ T ≤ 5. 1 ≤ N ≤ 5.

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

1 ≤ T ≤ 100. 1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어지며, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 정수 N이 있는 한 줄로 구성된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 게임을 끝내는 데 필요한 최소 라운드 수의 기댓값을 나타내는 유리수이다. y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참조한다.

예제 케이스 #1에서는 카드 세 장의 숫자가 모두 같으므로, 어떤 순서로 뒤집더라도 한 라운드 만에 게임이 끝난다.

예제 케이스 #2에서는 다음과 같다.

• 처음 뒤집은 카드 두 장이 서로 다르면 라운드가 끝나고 세 번째 카드를 뒤집을 수 없다. 그러면 다음 라운드에 아직 알지 못하는 카드 중 두 장을 더 뒤집을 수 있다.

• 두 카드가 일치하면 남은 세 번째 카드가 어디에 있는지 이미 알게 되고, 그다음 한 라운드를 더 사용하여 남은 트리오를 뒤집을 수 있으므로 총 세 라운드가 걸린다. 이 상황이 발생할 확률은 3/5 × 1/3 = 1/5이다.

• 그 외의 경우에는 두 번째 라운드가 끝나지만, 세 번째 라운드에 아직 알지 못하는 카드 하나를 더 뒤집고 나면 두 트리오를 모두 완성하는 방법을 알게 되므로 총 네 라운드가 걸린다. 이 상황이 발생할 확률은 3/5 × 2/3 = 2/5이다.

• 처음 뒤집은 카드 두 장이 같다면, 자세한 내용은 풀이자가 연습 문제로 풀어 보도록 남겨 둔다.

정답은 3 × 1/5 + 4 × 2/5 + ... = 17/5이다.