Observation Wheel

An observation wheel has $N$ gondolas arranged in a circle, and the wheel turns slowly. The gondolas pass the entrance one after another, and when a gondola passes the entrance, the person standing there may board it.

The gondolas in this problem are small, so each one holds a single person. If the gondola passing the entrance is already occupied, the waiting person waits for the next one. If that one is occupied too, she waits for the one after it, and so on until a free gondola arrives. Nobody ever gets off a gondola here. People only board, and after that they keep turning with the wheel for as long as we care about.

So that nobody is unhappy about a long wait, the fare works like this. When a person comes to the wheel and the first gondola to pass the entrance is free, she pays $N$ dollars for the ride. If the first gondola is occupied and she has to wait for the second one, she pays $N-1$ dollars. If the first two are occupied and she has to wait for the third one, she pays $N-2$ dollars. In general, a person who lets $K$ occupied gondolas go by before boarding pays $N-K$ dollars. In the worst case she lets all but one gondola go by and pays just 1 dollar.

People come to the wheel at random moments, so for each person the first gondola to pass the entrance is chosen uniformly at random, independently of everything before it. Nobody arrives while someone is already waiting, so there is never a queue. A person always 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 expected 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 '.' and 'X'. The length of the line is $N$. The $i$-th character is 'X' when the $i$-th gondola is already occupied and '.' when it is still free. The gondolas are numbered in the order they pass the entrance, so gondola 1 is followed by gondola 2, and after the last gondola the numbering starts over from gondola 1.

Limits

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

For each test case print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is the expected total amount of money in dollars. Round y to exactly 9 digits after the decimal point and print all 9 digits, trailing zeros included.

Take three gondolas where only the second one is occupied. There are nine equally likely outcomes, each with probability 1/9.

The first person comes. If the next gondola to pass the entrance is:

• the 1st gondola, which is free, she boards it and pays 3 dollars. Some time later the second person comes. If the next gondola to pass the entrance is:
  • the 1st gondola, which is occupied, and so is the 2nd, she waits for the 3rd and pays 1 dollar. In total we earn 4 dollars.
  • the 2nd gondola, which is occupied, she skips it, boards the 3rd and pays 2 dollars. In total we earn 5 dollars.
  • the 3rd gondola, which is free, she pays 3 dollars. In total we earn 6 dollars.
• the 2nd gondola, which is occupied, she skips it, boards the 3rd and pays 2 dollars. Some time later the second person comes. If the next gondola to pass the entrance is:
  • the 1st gondola, which is free, she pays 3 dollars. In total we earn 5 dollars.
  • the 2nd gondola, which is occupied, and so is the 3rd, she waits for the 1st and pays 1 dollar. In total we earn 3 dollars.
  • the 3rd gondola, which is occupied, she skips it, boards the 1st and pays 2 dollars. In total we earn 4 dollars.
• the 3rd gondola, which is free, she boards it and pays 3 dollars. Some time later the second person comes. If the next gondola to pass the entrance is:
  • the 1st gondola, which is free, she pays 3 dollars. In total we earn 6 dollars.
  • the 2nd gondola, which is occupied, and so is the 3rd, she waits for the 1st and pays 1 dollar. In total we earn 4 dollars.
  • the 3rd gondola, which is occupied, she skips it, boards the 1st and pays 2 dollars. In total we earn 5 dollars.

Among the nine outcomes we earn 3 dollars once, 4 dollars three times, 5 dollars three times, and 6 dollars twice, so the expected total is $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.666666666\ldots$ dollars, which is printed as 4.666666667.