까다로운 트리오

Tricky Trios 게임은 $3N$장의 카드 덱으로 진행한다. 숫자 1이 적힌 카드 3장, 숫자 2가 적힌 카드 3장, ..., 숫자 $N$이 적힌 카드 3장이 있다. 카드는 모든 순서가 같은 확률로 나오도록 섞은 뒤, 숫자가 보이지 않게 뒷면이 위로 오도록 테이블에 늘어놓는다.

각 라운드는 다음과 같이 진행한다.

• 카드 한 장을 골라 뒤집어 숫자를 확인한다.
• 두 번째 카드를 골라 뒤집는다. 숫자가 첫 번째 카드와 다르면 라운드가 끝나고, 세 번째 카드는 뒤집을 수 없다. 같으면 다음을 진행한다.
  • 세 번째 카드를 골라 뒤집는다. 숫자가 두 번째 카드와 다르면 라운드가 끝난다. 같으면 트리오를 찾은 것이므로 세 장을 게임에서 제거하고 라운드가 끝난다.

라운드가 끝났을 때 남은 카드가 없으면 게임에서 이긴다. 그렇지 않으면 다음 라운드를 시작하기 전에 뒤집힌 카드를 모두 다시 뒤집어 숫자를 가린다. 기억력이 아주 좋아서, 카드의 위치는 게임이 끝날 때까지 기억한다.

이미 숫자를 아는 카드라도 뒤집을 수 있다. 트리오를 이루는 세 장의 위치를 모두 알고 있더라도, 제거하려면 같은 라운드에서 세 장을 모두 뒤집어야 한다.

가능한 한 빨리 이기고 싶으므로, 게임이 끝나기까지 필요한 라운드 수의 기댓값을 최소로 만드는 전략을 쓴다. 그 기댓값은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 정수 $N$이 적힌 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 위에서 설명한 게임을 끝내는 데 필요한 라운드 수 기댓값의 최솟값인 유리수이다. $y$는 정답과 절댓값 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

$1 \le N \le 10^{9}$

예제 1번에서는 카드 3장의 숫자가 모두 같으므로, 어떤 순서로 뒤집어도 1 라운드에 게임이 끝난다.

예제 2번에서는 다음과 같다.

• 처음 뒤집은 두 카드의 숫자가 다르면 그 라운드는 끝나고 세 번째 카드는 뒤집을 수 없다. 그다음 라운드에 아직 모르는 카드 두 장을 더 뒤집는다.

  • 두 숫자가 같으면 남은 한 장의 위치는 이미 알고 있으므로, 라운드를 한 번 더 써서 남은 트리오를 뒤집는다. 전체 3 라운드가 걸린다. 이 경우의 확률은 $\frac{3}{5} \times \frac{1}{3} = \frac{1}{5}$이다.
  • 숫자가 다르면 두 번째 라운드는 끝나지만, 세 번째 라운드에 아직 모르는 카드를 한 장 더 뒤집으면 두 트리오를 모두 완성할 수 있다. 전체 4 라운드가 걸린다. 이 경우의 확률은 $\frac{3}{5} \times \frac{2}{3} = \frac{2}{5}$이다.

• 처음 뒤집은 두 카드의 숫자가 같은 경우의 세부 풀이는 독자에게 연습 문제로 남긴다.

답은 $3 \times \frac{1}{5} + 4 \times \frac{2}{5} + \cdots = \frac{17}{5}$이다.