你的出版社决定让猴子在键盘上随机敲击来创作伟大的文学作品。你负责监督一只猴子，它使用的键盘上有 $K$ 个按键，每个按键上都标有一个大写英文字母。（可能有多个按键显示相同的字母。）猴子将从一个空字符串开始，重复以下操作 $S$ 次：从键盘上均匀随机地选择一个按键并按下，将该按键对应的字母添加到字符串的末尾。最终生成的字符串长度为 $S$。

你有一个长度为 $L$ 的目标单词，你希望猴子能敲出它。（目标单词不一定是一个真实的英语单词。）这个目标单词在猴子敲出的内容中甚至可能出现多次。（重叠的情况也算在内——例如，如果目标单词是 "ABA"，而猴子敲出了 "ABABA"，则包含两次目标单词。）

你计划为猴子敲出的每一个目标单词支付一根香蕉。当你去检查猴子的工作时，你会带上最少数量的香蕉，以确保无论猴子敲出什么，你总是有足够的香蕉支付给它。然后，你会为猴子实际敲出的每一个目标单词支付一根香蕉。你会保留剩下的香蕉。

你预计能保留多少根香蕉？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含三行。第一行包含三个用空格分隔的正整数：$K$、$L$ 和 $S$。第二行包含一个长度为 $K$ 的大写英文字母字符串，表示猴子的键盘。第三行包含一个长度为 $L$ 的大写英文字母字符串，表示目标单词。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $y$ 是你支付给猴子后预计能保留的香蕉数量。

如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则被视为正确。请参阅 常见问题解答 以了解其含义以及我们接受的实数格式。

数据范围

$1 \le T \le 100$。

小数据集

$1 \le K \le 7$。 $1 \le L \le S \le 7$。

大数据集

$1 \le K \le 100$。 $1 \le L \le S \le 100$。

样例

输入 1

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

输出 1

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

说明

注意，Case #5 不在小数据集的范围内。

在 Case #1 中，猴子根本没有机会敲出目标单词 "MONKEY"（因为它的键盘缺少 "MONKEY" 中的大部分字母），所以你访问时不需要带任何香蕉，当然也不用支付。可怜的猴子！

在 Case #2 中，猴子保证会敲出 "AAAA"，其中包含两次重叠的目标单词 "AAA"。你会带上两根香蕉，然后全部支付出去。

在 Case #3 中，猴子以相等的概率（各 1/4）产生以下输出："AA"、"AB"、"BA"、"BB"。它们分别包含 0、1、1 和 2 次目标单词。你必须带上 2 根香蕉以应对 "BB" 的情况，但平均而言，你支付的香蕉数量为 $(0 + 1 + 1 + 2) / 4 = 1$。

在 Case #4 中，猴子第一次敲出 "G" 的概率为 1/3，第二次敲出 "O" 的概率为 1/3，因此敲出 "GO" 的概率为 1/9。你会带上一根香蕉，并有 1/9 的概率将其支付出去。

在 Case #5 中，猴子理论上最多可以敲出九次 "ROSENCRANTZ"，但即使敲出一次的概率也非常小，以至于与答案的可接受误差范围相比可以忽略不计。