Một vòng quay quan sát bao gồm \(N\) cabin chở khách được sắp xếp thành một vòng tròn, quay chậm rãi. Các cabin lần lượt đi qua lối vào, và khi một cabin đi qua lối vào, một người có thể bước vào cabin đó.

Trong bài toán này, các cabin nhỏ đến mức mỗi cabin chỉ có thể chở đúng một người. Vì vậy, nếu cabin đi qua lối vào đã có người, người đang đợi ở lối vào sẽ phải đợi cabin tiếp theo đến. Nếu cabin đó cũng đã có người, người đó sẽ phải đợi cabin tiếp theo nữa, và cứ thế, cho đến khi một cabin trống xuất hiện. Để đơn giản, chúng ta sẽ không xem xét việc mọi người rời khỏi cabin — hãy giả sử rằng tất cả những gì mọi người làm là bước vào cabin, và sau đó quay cùng vòng quay trong một thời gian dài tùy ý.

Chúng tôi muốn đảm bảo mọi người không thất vọng vì thời gian chờ đợi lâu, và vì vậy chúng tôi đã giới thiệu một sơ đồ giá linh hoạt: khi một người tiếp cận vòng quay, và cabin đầu tiên đi qua lối vào là cabin trống, cô ấy trả \(N\) đô la cho chuyến đi. Nếu cabin đầu tiên đã có người và cô ấy phải đợi cabin thứ hai, cô ấy trả \(N-1\) đô la cho chuyến đi. Nếu hai cabin đầu tiên đã có người và cô ấy phải đợi cabin thứ ba, cô ấy trả \(N-2\) đô la cho chuyến đi. Nói chung, nếu cô ấy phải đợi \(K\) cabin đã có người đi qua, cô ấy trả \(N-K\) đô la. Trong trường hợp xấu nhất, khi cô ấy phải đợi tất cả trừ một cabin đi qua, cô ấy sẽ chỉ trả 1 đô la.

Hãy giả sử rằng mọi người tiếp cận vòng quay của chúng ta tại các thời điểm ngẫu nhiên, vì vậy đối với mỗi người tiếp cận vòng quay, cabin đầu tiên đi qua lối vào được chọn ngẫu nhiên và độc lập. Hãy cũng giả sử rằng không ai đến vòng quay khi đã có ít nhất một người đang đợi để vào, để chúng ta không phải xử lý việc xếp hàng. Một người sẽ luôn đi cabin trống đầu tiên đi qua lối vào.

Bạn được cho số lượng cabin và những cabin nào đã có người. Chúng ta sẽ kiếm được trung bình bao nhiêu tiền cho đến khi tất cả các cabin đều có người?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo. Mỗi dòng mô tả một bộ test và chỉ chứa các ký tự '.' (dấu chấm) hoặc 'X' (chữ cái X viết hoa). Số lượng ký tự trong dòng này cho bạn biết \(N\). Ký tự thứ \(i\) là 'X' khi cabin thứ \(i\) đã có người, và '.' khi nó vẫn còn trống. Các cabin được đánh số theo thứ tự chúng đi qua lối vào, vì vậy cabin thứ 1 được tiếp nối bởi cabin thứ 2, và cứ thế, bắt đầu lại từ đầu sau khi cabin cuối cùng đi qua.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số tiền trung bình chúng ta sẽ nhận được, tính bằng đô la. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-9}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 50\).

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 20\).
• Test set 2 (Hidden): \(1 \le N \le 200\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
.X.
X.X.
.XX.
X..XX.
.XX..X

Case #1: 4.66666666666667
Case #2: 6.00000000000000
Case #3: 5.75000000000000
Case #4: 13.4722222222222
Case #5: 13.5277777777778

Nguồn

Google Code Jam 2013, Vòng 3, bài Observation Wheel.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.