Nhà xuất bản của bạn quyết định dùng những con khỉ gõ bàn phím ngẫu nhiên để viết nên các tác phẩm văn học vĩ đại. Bạn giám sát một con khỉ có bàn phím gồm \(K\) phím, mỗi phím mang một chữ cái tiếng Anh viết hoa. (Nhiều phím có thể mang cùng một chữ.)

Con khỉ bắt đầu với chuỗi rỗng và lặp thao tác sau \(S\) lần: chọn đều ngẫu nhiên một phím rồi nhấn nó, thêm một bản sao chữ trên phím vào cuối chuỗi bên phải. Chuỗi cuối cùng dài \(S\).

Bạn có một từ mục tiêu dài \(L\) mà mình hy vọng con khỉ sẽ gõ. (Từ này không nhất thiết là một từ tiếng Anh thật.) Từ mục tiêu có thể xuất hiện nhiều lần trong chuỗi con khỉ gõ. Các lần xuất hiện chồng lấn cũng được tính; chẳng hạn, nếu từ mục tiêu là ABA và con khỉ gõ ABABA, chuỗi đó chứa hai lần xuất hiện.

Bạn định trả cho khỉ một quả chuối cho mỗi lần xuất hiện của từ mục tiêu. Khi đến kiểm tra, bạn mang theo số chuối ít nhất cần thiết để bảo đảm luôn đủ trả, bất kể nó đã gõ gì. Sau đó, bạn trả một quả cho mỗi lần từ mục tiêu thực sự xuất hiện và giữ lại số chuối còn thừa.

Kỳ vọng số chuối bạn giữ lại là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa ba số nguyên dương \(K\), \(L\), \(S\). Dòng thứ hai chứa chuỗi \(K\) chữ cái tiếng Anh viết hoa mô tả bàn phím. Dòng thứ ba chứa chuỗi \(L\) chữ cái tiếng Anh viết hoa là từ mục tiêu.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(y\) là kỳ vọng số chuối bạn giữ lại sau khi trả cho khỉ.

Kết quả được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án không vượt quá \(10^{-6}\).

Ràng buộc

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

Phân nhóm

• Test Set 1 (Nhỏ): \(1 \le K \le 7\), \(1 \le L \le S \le 7\).
• Test Set 2 (Lớn): \(1 \le K \le 100\), \(1 \le L \le S \le 100\).

Đ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
7 6 6
BANANAS
MONKEY
2 3 4
AA
AAA
2 1 2
AB
B
6 2 2
GOOGLE
GO
26 11 100
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ROSENCRANTZ

    ???+ success "Output"

        ```sample
Case #1: 0.0
Case #2: 0.0
Case #3: 1.0
Case #4: 0.8888889
Case #5: 9.0

??? "Giải thích"

    Lưu ý Case #5 không nằm trong giới hạn của bộ Nhỏ.

    Trong Case #1, con khỉ không có cơ hội gõ từ `MONKEY` dù chỉ một lần vì bàn phím thiếu phần lớn chữ trong từ đó. Bạn không mang quả chuối nào và dĩ nhiên cũng không trả quả nào. Tội nghiệp chú khỉ!

    Trong Case #2, con khỉ chắc chắn gõ `AAAA`, chứa hai lần xuất hiện chồng lấn của `AAA`. Bạn mang hai quả rồi trả cả hai.

    Trong Case #3, bốn kết quả `AA`, `AB`, `BA`, `BB` có xác suất bằng nhau, mỗi kết quả là $1/4$. Chúng lần lượt chứa 0, 1, 1, 2 lần xuất hiện của từ mục tiêu. Bạn phải mang 2 quả để sẵn sàng cho trường hợp `BB`, nhưng trung bình trả $(0+1+1+2)/4=1$ quả.

    Trong Case #4, xác suất ký tự đầu là `G` bằng $1/3$, và xác suất ký tự thứ hai là `O` bằng $1/3$, nên xác suất gõ `GO` là $1/9$. Bạn mang một quả và phải trao nó trong $1/9$ số lần.

    Trong Case #5, về lý thuyết con khỉ có thể gõ `ROSENCRANTZ` tới chín lần, nhưng xác suất nó xuất hiện dù chỉ một lần nhỏ đến mức không đáng kể so với biên sai số được chấp nhận.

Nguồn

Google Code Jam 2015, Vòng 1C, bài Typewriter Monkey.

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