Typewriter Monkey

Your publishing house has decided to have monkeys type randomly at keyboards to write great works of literature. You supervise one monkey. Its keyboard has $K$ keys, and each key is labeled with an uppercase English letter. Several keys may show the same letter.

The monkey starts with an empty string and repeats the following $S$ times: it picks one key of the keyboard uniformly at random, presses it, and appends that key's letter to the right end of the string. The final string has length $S$.

You have a target word of length $L$ that you hope the monkey types. The target word is not necessarily a real English word. It may appear several times in what the monkey types, and overlapping occurrences each count. For example, if the target word is "ABA" and the monkey types "ABABA", the target word occurs twice.

You pay the monkey one banana for every occurrence of the target word. When you go to inspect the monkey's work, you bring the smallest number of bananas that is always enough to pay the monkey, no matter what it typed. Then you pay one banana per occurrence that the monkey actually typed, and you keep the rest.

Compute the expected number of bananas you keep.

The first line contains the number of test cases $T$. Each test case consists of three lines. The first line contains three positive integers $K$, $L$, and $S$, separated by spaces. The second line contains a string of $K$ uppercase English letters describing the monkey's keyboard. The third line contains a string of $L$ uppercase English letters describing the target word.

Limits

• $1 \le T \le 100$
• $1 \le K \le 100$
• $1 \le L \le S \le 100$

For each test case, print one line of the form Case #x: y, where $x$ is the test case number and $y$ is the expected number of bananas you keep after paying the monkey.

Print $y$ with exactly six digits after the decimal point. Round at the seventh digit, and round a value that is exactly halfway up.

In the first case the keyboard BANANAS is missing most letters of MONKEY, so the monkey has no chance of typing the target word. You bring no bananas and you pay none.

In the second case the monkey certainly types AAAA, which contains two overlapping occurrences of AAA. You bring two bananas and pay both.

In the third case the monkey produces AA, AB, BA, and BB with probability $1/4$ each, and the target word occurs 0, 1, 1, and 2 times. You must bring two bananas for the BB case, but on average you pay $(0 + 1 + 1 + 2) / 4 = 1$.

In the fourth case the first letter is G with probability $1/3$ and the second letter is O with probability $1/3$, so the monkey types GO with probability $1/9$. You bring one banana and give it away $1/9$ of the time.

In the fifth case the monkey could in theory type ROSENCRANTZ nine times, but the probability is far too small to show up in six decimal places.