Tricky Trios

The game of Tricky Trios is played with a deck of $3N$ cards. There are three cards labeled 1, three cards labeled 2, and so on, up to three cards labeled $N$. The cards are shuffled so that every ordering is equally likely, then dealt face down onto a table so that all the numbers are hidden.

Each round proceeds as follows:

• Choose one card and flip it over to reveal its number.
• Choose a second card and flip it over. If its number differs from the first card's number, the round ends and you may not flip a third card. Otherwise:
  • Choose a third card and flip it over. If its number differs from the second card's number, the round ends. Otherwise, you have found a trio, so you remove all three cards from the game, and the round ends.

When a round ends, if no cards remain, you win. Otherwise, before the next round, you flip all revealed cards back over to hide their numbers. You have an amazing memory, so you remember where they are for the rest of the game.

You may flip a card even if you already know its number. Also, even if you know the locations of all three cards in a trio, you must flip all three in the same round to remove it.

You want to win as quickly as possible, so you use a strategy that minimizes the expected number of rounds needed to end the game. What is that expected number of rounds?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of one line with an integer $N$, as described above.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is a rational number: the minimal expected number of rounds needed to end the game, as described above. $y$ is considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

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

In Sample Case #1, all three cards have the same number, so flipping them over in any order ends the game in one round.

In Sample Case #2:

• If the first two cards flipped are different, the round ends and no third card can be flipped. Then the next round flips over two more of the unknown cards.

  • If they match, the remaining third card's location is already known, so one more round flips the remaining trio, for three rounds total. The probability of this is $\frac{3}{5} \times \frac{1}{3} = \frac{1}{5}$.
  • Otherwise, the second round ends, but after flipping another unknown card on the third round, both trios can be finished, for four rounds total. The probability of this is $\frac{3}{5} \times \frac{2}{3} = \frac{2}{5}$.

• If the first two cards flipped are the same, the details are left as an exercise for the solver.

The answer is $3 \times \frac{1}{5} + 4 \times \frac{2}{5} + \cdots = \frac{17}{5}$.