Typewriter Monkey (Small)

A publishing house decided to produce literature by letting a monkey hit keys at random. The monkey's keyboard has $K$ keys, and each key is labeled with one uppercase English letter. Several keys can carry the same letter.

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

You have a target word of length $L$. It does not have to be a real English word. The target word can appear several times in what the monkey types, and overlapping occurrences are counted separately. If the target word is ABA and the monkey types ABABA, the number of occurrences is 2.

You pay the monkey one banana for each occurrence of the target word. When you go to inspect the work, you bring the smallest number of bananas that is always enough, no matter what the monkey typed. That is, you bring as many bananas as the largest number of occurrences that a length $S$ string typed on this keyboard can contain. Then you pay one banana per occurrence in the string the monkey actually typed, and you keep the rest.

Find the expected number of bananas you get to keep.

The first line contains the number of test cases $T$. Each test case consists of three lines. The first line contains the 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 7$
• $1 \le L \le S \le 7$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the expected number of bananas you get to keep. Print $y$ rounded to six digits after the decimal point, with all six digits shown. Under these limits the answer never lands exactly on a rounding tie.