Description

你的出版社决定让猴子随机敲击键盘来创作伟大的文学作品。你是一个猴子的监督员，这只猴子的键盘上有 $K$ 个按键，每个按键上都标有一个大写英文字母（同一个字母可能出现在多个按键上）。猴子将从一个空字符串开始，重复 $S$ 次以下操作：从键盘上等概率随机选择一个按键并按下，将该按键上的字母添加到字符串的末尾。最终得到的字符串长度为 $S$。

你有一个长度为 $L$ 的目标单词，你希望猴子能够敲出来（目标单词不一定是真正的英文单词）。这个目标单词可能在猴子敲出的字符串中出现多次（重叠的情况也算，例如目标单词为 "ABA"，猴子敲出 "ABABA" 时，包含两个 "ABA"）。

你打算每出现一次目标单词就给猴子一根香蕉。当你去检查猴子的作品时，你会带上足够多的香蕉，以保证无论猴子敲出了什么，你都能支付得起。然后，你会根据猴子实际敲出的目标单词次数支付香蕉，剩下的香蕉归你所有。

你期望最终能留下多少根香蕉？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含三行：

第一行包含三个用空格分隔的正整数：$K$、$L$ 和 $S$。

第二行为一个长度为 $K$ 的仅包含大写英文字母的字符串，表示猴子的键盘。

第三行为一个长度为 $L$ 的仅包含大写英文字母的字符串，表示目标单词。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为你期望能留下的香蕉数。

如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

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

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

Hint

样例解释

注意，第 5 组样例不在 Small 数据集的范围内。

在第 1 组样例中，猴子根本无法敲出目标单词 "MONKEY"（因为键盘上缺少目标单词中的大部分字母），所以你无需带香蕉，也不会支付任何香蕉。可怜的猴子！

在第 2 组样例中，猴子一定会敲出 "AAAA"，其中目标单词 "AAA" 会出现两次（重叠），你需要带两根香蕉并全部支付出去。

在第 3 组样例中，猴子可能敲出的字符串有 "AA"、"AB"、"BA"、"BB"，每种概率均为 $1/4$，它们分别包含 0、1、1、2 次目标单词。你需要带两根香蕉以备 "BB" 的情况，但平均支付 $(0 + 1 + 1 + 2) / 4 = 1$ 根香蕉。

在第 4 组样例中，猴子第一步有 $1/3$ 的概率敲 "G"，第二步有 $1/3$ 的概率敲 "O"，所以敲出 "GO" 的概率为 $1/9$，你需要带一根香蕉，并在 $1/9$ 的情况下支付出去。

在第 5 组样例中，理论上猴子最多能敲出 9 次 "ROSENCRANTZ"，但实际出现一次的概率都极小，可以忽略不计。

数据范围

$1 \leq T \leq 100$。

小数据集（11 分）

• 时间限制：240 5 秒。
• $1 \leq K \leq 7$。
• $1 \leq L \leq S \leq 7$。

大数据集

• 时间限制：480 10 秒。
• $1 \leq K \leq 100$。
• $1 \leq L \leq S \leq 100$。

由 ChatGPT 4.1 翻译