题目描述
一个观景摩天轮由 $N$ 个排成圆环的乘客吊舱组成，摩天轮正在缓慢旋转。吊舱会依次经过入口，当一个吊舱经过入口时，乘客可以进入该吊舱。
在本题中，吊舱非常小，每个吊舱只能容纳一人。因此，如果经过入口的吊舱已经有人，在入口等待的乘客就必须等待下一个吊舱到来。如果下一个吊舱也已经有人，乘客就必须继续等待，直到一个空吊舱到来。为简化起见，我们不考虑乘客离开吊舱的情况——假设人们只会进入吊舱，并在摩天轮上旋转任意长的时间。
为了确保人们不会因为等待时间过长而感到失望，我们引入了一种灵活的定价方案：当一个人来到摩天轮前，如果第一个经过入口的吊舱是空的，她支付 $N$ 美元。如果第一个吊舱已满，她必须等待第二个吊舱，她支付 $N-1$ 美元。如果前两个吊舱都已满，她必须等待第三个吊舱，她支付 $N-2$ 美元。通常情况下，如果她必须等待 $K$ 个已满的吊舱经过，她支付 $N-K$ 美元。在最坏的情况下，如果她必须等待除最后一个吊舱外的所有吊舱经过，她只需支付 1 美元。
假设人们在随机的时间点来到摩天轮前，因此对于每个来到摩天轮前的人，第一个经过入口的吊舱是均匀且独立地选取的。同时假设在已经有人等待进入时，不会有其他人来到摩天轮前，这样我们就不需要处理排队问题。乘客总是会乘坐第一个经过入口的空吊舱。
给定吊舱的总数以及哪些吊舱已经有人，请计算在所有吊舱都被占满之前，我们平均能赚多少钱。
输入格式
输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行描述一个测试用例，仅包含 '.'（点）或 'X'（大写字母 X）字符。该行字符的数量即为 $N$。如果第 $i$ 个字符为 'X'，表示第 $i$ 个吊舱已被占用；如果为 '.'，则表示该吊舱仍为空。吊舱按经过入口的顺序编号，即第 1 个吊舱之后是第 2 个，依此类推，最后一个吊舱之后又回到第 1 个。
输出格式
对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是我们平均能赚到的金额（单位为美元）。绝对误差或相对误差不超过 $10^{-9}$ 的答案将被接受。
数据范围
$1 \le T \le 50$。
小数据（测试集 1 - 可见；8 分）
$1 \le N \le 20$。
大数据（测试集 2 - 隐藏；23 分）
$1 \le N \le 200$。
样例
样例输入 1
5 .X. X.X. .XX. X..XX. .XX..X
样例输出 1
Case #1: 4.66666666666667 Case #2: 6.00000000000000 Case #3: 5.75000000000000 Case #4: 13.4722222222222 Case #5: 13.5277777777778
说明
以下是第一个样例的计算过程。共有九种可能性，每种概率为 $1/9$：
第一个人来到。如果下一个经过入口的吊舱是：
第 1 个吊舱（空）：第一个人进入并支付 3 美元。随后，第二个人来到。如果下一个经过入口的吊舱是：
- 第 1 个吊舱（已满），且第 2 个吊舱也已满，第二个人必须等到第 3 个吊舱，因此在进入前她支付 1 美元。总计赚取 4 美元。
- 第 2 个吊舱（已满），第二个人必须跳过它并进入第 3 个吊舱，因此支付 2 美元。总计赚取 5 美元。
- 第 3 个吊舱（空），第二个人支付 3 美元。总计赚取 6 美元。
第 2 个吊舱（已满）：第一个人必须跳过它并进入第 3 个吊舱，支付 2 美元。随后，第二个人来到。如果下一个经过入口的吊舱是：
- 第 1 个吊舱（空），第二个人支付 3 美元。总计赚取 5 美元。
- 第 2 个吊舱（已满，第 3 个也已满），第二个人必须等到第 1 个吊舱，因此在进入前她支付 1 美元。总计赚取 3 美元。
- 第 3 个吊舱（已满），第二个人必须跳过它并进入第 1 个吊舱，因此支付 2 美元。总计赚取 4 美元。
第 3 个吊舱（空）：第一个人进入并支付 3 美元。随后，第二个人来到。如果下一个经过入口的吊舱是：
- 第 1 个吊舱（空），第二个人支付 3 美元。总计赚取 6 美元。
- 第 2 个吊舱（已满，第 3 个也已满），第二个人必须等到第 1 个吊舱，因此在进入前她支付 1 美元。总计赚取 4 美元。
- 第 3 个吊舱（已满），第二个人必须跳过它并进入第 1 个吊舱，因此支付 2 美元。总计赚取 5 美元。
我们有九种可能性，其中一种赚取 3 美元，三种赚取 4 美元，三种赚取 5 美元，两种赚取 6 美元。平均赚取 $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6) / 9 = 42 / 9 \approx 4.6666666666$ 美元。