Water?

One of the main goals of sending the Curiosity rover to Mars is to look for more evidence that Mars may have had water on its surface in the past, or perhaps still does today. To decide whether water was present, scientists rely on clues in the images, such as rust and other signs of oxidation. In this problem you examine pictures of the Martian surface and find evidence of water in them if it exists.

Each picture is given as a rectangle of $h \times w$ pixels, with $1 \le h, w \le 50$. Every pixel indicates a type of material, written as one upper-case letter from A to Z (no other characters appear). Some of these letters are marked as special: they are the clues for water. Given a minimum size $m$ with $1 \le m \le \min(h, w)$, find the largest density of special letters over all axis-aligned subrectangles whose height and width are both at least $m$.

The density of a rectangle is the number of special pixels it contains divided by its total number of pixels.

The first line contains the number $K$ of data sets. Each of the $K$ data sets has the following form:

• One line with three integers $h$, $w$, $m$: the image height, the image width, and the minimum rectangle size.
• One line with a string of $1$ to $26$ distinct upper-case letters (A–Z, not necessarily sorted). These are the special, water-indicating letters.
• $h$ lines follow, each consisting of exactly $w$ upper-case letters describing one row of the image.

For each data set, print Data Set x: on its own line, where $x$ is the data set number (starting from $1$). On the next line print the maximum density as a fraction a/b, where $a$ is the number of special pixels and $b$ is the total number of pixels of the chosen rectangle, considering only rectangles whose height and width are both at least $m$.

The fraction is written exactly as counted and is not reduced (for example 8/16, not 1/2). If several rectangles reach the same maximum density, choose the one with the largest total number of pixels $b$; this makes the answer unique.

Separate consecutive data sets with a blank line.