Funniest Word Search

Siv's birthday is next week, and Cel is preparing a birthday present for her. Because Siv loves puzzles, Cel is making a word search puzzle as the gift.

In a word search puzzle, the solver gets a rectangular grid with R rows and C columns and must find all valid words hidden inside it. Each hidden word may appear horizontally or vertically (but not diagonally), forward or in reverse. Hidden words may overlap.

Cel has a dictionary of W different words. These are the only words that can be hidden in the grid. Not every horizontal or vertical part of the grid necessarily contains one of the hidden words. The words are not necessarily real English words. Each word may appear in the grid once or more, or not at all.

Cel has already made the puzzle, but it is too big to print on one sheet of paper. Siv's birthday is coming soon, so there is not enough time to build a new puzzle from scratch. Cel wants to shrink the grid by selecting a non-empty subgrid that is aligned to the original grid lines.

A random subgrid might give a boring puzzle with few hidden words. So Cel wants the subgrid with the largest fun value, defined as:

$\text{fun value} = \frac{\text{total length of matched words}}{\text{width of subgrid} + \text{height of subgrid}}$

Notes:

• The entire word must appear in the subgrid to be counted.
• If a word appears x times in the subgrid, its length is added x times in the formula.
• If a word and its reverse both appear in the subgrid (even at the same position), both occurrences are counted.
• The subgrid with the largest fun value may be the entire original grid.

Help Cel find the largest fun value a subgrid can have, and the number of different subgrids that reach that value. Two subgrids are different if and only if some cell (row, column position) is in one subgrid but not the other.

The first line contains the number of test cases, T. T test cases follow, each structured as below.

• The first line contains three integers R, C and W, as described above.
• Each of the next R lines contains exactly C uppercase English letters.
• Each of the next W lines contains exactly one valid word. Each word contains only uppercase English letters.

For each test case, output one line in the form Case #x: y/z n, where:

• x is the test case number, starting from 1.
• y/z is the largest possible fun value of a subgrid, written as an irreducible fraction. y is a non-negative integer and z is a positive integer.
• n is the number of subgrids whose fun value equals y/z.

The greatest common divisor of y and z is 1.

• 1 ≤ T ≤ 100.
• 1 ≤ R ≤ 100.
• 1 ≤ C ≤ 100.
• No word appears more than once in the list of valid words.
• The combined length of all words in the list of valid words is at most 5000 letters.