题目描述

住房部正在规划一个大型的住房小区建设项目。每个小区包含若干套公寓，将以合理的价格出售给政府雇员。该部门已经选定了几块 $m \times n$ 大小的土地，每块土地都有可能用于建设一个小区。这些土地都是矩形的，每块土地由 $m \times n$ 个 $1 \times 1$ 的正方形地块组成。所有的住房小区都是 $h \times w$ 的矩形，正好覆盖每块土地中的 $h \times w$ 个地块。

问题在于，原本有些土地上存在一些旧建筑，每栋旧建筑恰好占据一个地块，这使得无法为所有小区找到足够的空地来启动项目。因此，住房部必须购买其中一些建筑并拆除，以腾出所需的空间。这些旧建筑属于一些业主。这些业主对他们的建筑可能被购买和拆除感到愤怒，特别是因为政府通常支付的价格远低于市场价格。

为了回应抗议，住房部宣布了一项“公平”的决定：如果要在某块土地上购买建筑，只会选择属于同一业主的建筑，并以合理的价格全部收购。同时，承诺不会在其他土地上购买属于同一业主的建筑。请注意，由于这一限制，可能会有一些土地无法建设小区。为了遵守承诺，住房部要求你编写一个程序，计算在这些条件下最多可以建设多少个住房小区。

输入

输入文件的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量，随后是每个测试用例的输入数据。每个测试用例的第一行包含五个整数：$k$（$1 \leq k \leq 30$），表示土地的数量；$m$ 和 $n$（$1 \leq m, n \leq 50$），分别表示每块土地的行数和列数；$h$ 和 $w$（$1 \leq h, w \leq 50$），表示一个小区所占的行数和列数。第一行之后，输入中会有 $k \times m$ 行，代表 $k$ 块土地，每块土地用一个 $m \times n$ 的矩阵表示。每行包含一个长度为 $n$ 的字符串，没有前导或尾随空格。字符串中的每个字符代表土地中的一个地块，可能是大写字母 A 到 Z，表示该地块的业主，或者字符 0，表示该地块为空。

输出

每个测试用例应输出一行，包含该测试用例下最多可以建设的住房小区的数量。

输入样例

2 
3 4 3 3 2 
A0B 
000 
0A0 
00B 
AA0 
00B 
0B0 
000 
A0A 
000 
B00 
B00 
3 4 3 3 2 
A0B 
000 
0A0 
00B 
AA0 
00B 
0B0 
000 
A0A 
000 
0B0 
B00 

输出样例

3
2 

题目来源

德黑兰 2002 年竞赛题目