Housing Complexes

The Ministry of Housing is planning a huge construction project consisting of several housing complexes. Each complex contains several apartments to be sold to government employees at reasonable prices. The ministry has secured several large plots of land for the project and wants to build exactly one complex on each plot. Every plot is a rectangle divided into $m \times n$ square blocks of size $1 \times 1$. Every housing complex is an $h \times w$ rectangle that covers exactly $h \times w$ blocks of the plot it is built on.

The difficulty is that each plot originally contains some old buildings — each building occupies exactly one block — so there may not be enough free space to place a complex. The ministry must therefore buy some of these buildings and demolish them to free the required space. The old buildings belong to a number of different owners.

In response to protests, the ministry announced the following "fair" policy: when it buys buildings on a plot, it will choose only buildings that belong to a single owner and buy all of them at a reasonable price; and it promises never to buy buildings belonging to that same owner on any other plot. Because of this constraint, there may be plots on which building a complex is impossible.

In other words, on each plot you may demolish the buildings of at most one owner, and across the whole project the buildings of any single owner may be bought on at most one plot. Determine the maximum number of housing complexes that can be built under these conditions.

The first line contains a single integer $t$ ($1 \le t \le 10$), the number of test cases. The data for each test case follows.

The first line of each test case contains five integers $k$, $m$, $n$, $h$, and $w$: $k$ ($1 \le k \le 30$) is the number of plots, $m$ and $n$ ($1 \le m, n \le 50$) are the number of rows and columns of each plot, and $h$ and $w$ ($1 \le h, w \le 50$) are the number of rows and columns a complex occupies.

The next $k \times m$ lines describe the $k$ plots, each as an $m \times n$ matrix. Each line is a string of length $n$ with no leading or trailing spaces. Each character is a block of the plot: an uppercase letter from A to Z denotes the owner of that block, and the character 0 (the digit zero) denotes a free block. The same letter denotes the same owner on every plot.

For each test case, print a single line containing the maximum number of housing complexes that can be built for that test case.