Observation Wheel (Large)

An observation wheel has $N$ gondolas arranged in a circle, and the wheel turns slowly. The gondolas pass the entrance one at a time, and a visitor waiting at the entrance may board the gondola that is passing.

Each gondola holds one person. If the gondola passing the entrance is already occupied, the visitor waits for the next one, then for the one after that, and so on until a free gondola arrives. Nobody ever leaves a gondola here. A rider just keeps turning with the wheel.

The price depends on the wait. If the first gondola to pass the entrance is free, the visitor pays $N$ dollars for the ride. If that first gondola is occupied and the visitor has to wait for the second one, the price is $N-1$ dollars. If the first two are occupied and the visitor boards the third, the price is $N-2$ dollars. In general, a visitor who lets $K$ occupied gondolas go by pays $N-K$ dollars. In the worst case the visitor lets all gondolas but one go by and pays 1 dollar.

Visitors arrive at random moments, so for each visitor the first gondola to pass the entrance is drawn uniformly at random among the $N$ gondolas, independently of the other visitors. Nobody arrives while someone is still waiting to board, so no queue forms. Every visitor boards the first free gondola that passes the entrance.

You are given the number of gondolas and which of them are already occupied. Compute the average total amount of money collected until every gondola is occupied.

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case and contains only the characters '.' (dot) and 'X' (capital letter X). The length of the line is $N$. The $i$-th character is 'X' if the $i$-th gondola is already occupied, and '.' if it is still free. The gondolas are numbered in the order they pass the entrance, so the 1st gondola is followed by the 2nd, and after the last gondola the 1st comes around again.

• $1 \le T \le 50$
• $1 \le N \le 200$

For each test case, print one line of the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the average amount of money collected, in dollars. Print $y$ rounded to exactly six digits after the decimal point.

Here is where the answer for the wheel .X. comes from. It has three gondolas and the 2nd one is occupied, so two visitors arrive, and each of them meets one of the three gondolas first. That gives nine outcomes, each of probability $1/9$.

The first visitor meets the 1st gondola, which is free, and pays 3 dollars. Then the second visitor arrives:

• the second visitor meets the 1st gondola, which is occupied, and the 2nd is occupied too, so the second visitor boards the 3rd and pays 1 dollar. Total: 4 dollars.
• the second visitor meets the 2nd gondola, which is occupied, so the second visitor boards the 3rd and pays 2 dollars. Total: 5 dollars.
• the second visitor meets the 3rd gondola, which is free, and pays 3 dollars. Total: 6 dollars.

The first visitor meets the 2nd gondola, which is occupied, so the first visitor boards the 3rd and pays 2 dollars. Then the second visitor arrives:

• the second visitor meets the 1st gondola, which is free, and pays 3 dollars. Total: 5 dollars.
• the second visitor meets the 2nd gondola, which is occupied, and the 3rd is occupied too, so the second visitor boards the 1st and pays 1 dollar. Total: 3 dollars.
• the second visitor meets the 3rd gondola, which is occupied, so the second visitor boards the 1st and pays 2 dollars. Total: 4 dollars.

The first visitor meets the 3rd gondola, which is free, and pays 3 dollars. Then the second visitor arrives:

• the second visitor meets the 1st gondola, which is free, and pays 3 dollars. Total: 6 dollars.
• the second visitor meets the 2nd gondola, which is occupied, and the 3rd is occupied too, so the second visitor boards the 1st and pays 1 dollar. Total: 4 dollars.
• the second visitor meets the 3rd gondola, which is occupied, so the second visitor boards the 1st and pays 2 dollars. Total: 5 dollars.

One outcome earns 3 dollars, three earn 4 dollars, three earn 5 dollars, and two earn 6 dollars, so the average is $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.666666\ldots$ dollars.