Sea Dragons

Sea dragons belong to the same larger family as sea horses and pipefish. They drift along slowly and rely on camouflage, and a leafy sea dragon does everything it can to look like a floating piece of kelp. That makes them hard to spot for a photo, and hard to find again in a photo you already took. So you will write software that counts the sea dragons in a picture.

You are given a two dimensional picture showing what a sea dragon looks like. The pixels forming the sea dragon are all connected by horizontal and vertical moves. You are then given another picture, and you count how many sea dragons occur in it.

Count only sea dragons that are entirely visible and look exactly like the sample, except that one may be closer to the camera and therefore bigger. A bigger sea dragon picture comes from a smaller one by replacing each pixel with a $2 \times 2$ square of pixels, or a $3 \times 3$ square, and so on. Within one sea dragon all those squares have the same size. Do not count rotated or mirrored versions.

One object in the picture is one maximal group of 'X' cells joined by horizontal and vertical moves. A group counts as one sea dragon when it matches the sample scaled by some factor $k$ exactly, with no cell missing and no cell added. Two dragons that touch therefore form one group and neither one counts. A separate group that happens to lie inside the bounding box of a dragon does not stop that dragon from counting.

The first line contains the number $K$ ($K \ge 1$) of data sets in the file. It is followed by $K$ data sets of the following form.

The first line of a data set contains four positive integers $h_s$, $w_s$, $h_p$, $w_p$. Here $h_s \times w_s$ ($1 \le h_s, w_s \le 20$) is the size of the sea dragon sample, $h_s$ being the height and $w_s$ the width. $h_p \times w_p$ ($1 \le h_p, w_p \le 100$) is the size of the picture you search.

Then come $h_s$ lines of exactly $w_s$ characters each, where each character is either '.' or 'X'. The 'X' characters make up the sea dragon. You can get from any 'X' of the sample to any other 'X' by moving horizontally and vertically over 'X' characters only, and there is at least one 'X'.

Then come $h_p$ lines of exactly $w_p$ characters each, again '.' or 'X'. In this image a sea dragon only occurs when it is not missing any spot and does not have any extraneous parts, so a shape that touches something else or is partly hidden is not counted.

For each data set, first output Data Set x: on a line by itself, where x is the number of the data set counting from 1. Then output the number of sea dragons the picture contains.

Follow each data set with one blank line.