The Proper Key

Long ago, a two-dimensional lock guarded the entrance to a pyramid. The lock was a flat wooden board divided into a grid of square fields arranged in regular rows and columns. Each field is either solid wood or empty.

The key for the lock is also two-dimensional: a single connected piece built from unit squares of the same size as the lock's fields. The key is inserted into the lock from the top and behaves like a falling Tetris piece: it may only move down or slide sideways (left or right). It can never move up and it can never be rotated.

Archaeologists have several candidate keys and want to try the most promising ones first, so they need to know how deep each key can be pushed into a given lock. Write a program that computes this depth.

The first line contains an integer T, the number of test cases.

Each test case is given as follows.

• A line with two integers R and C (1 ≤ R, C ≤ 100), the number of rows and columns of the key.
• R lines follow, each with exactly C characters describing the key. A # marks a wooden unit square and a . marks empty space. The wooden squares form one connected piece, and the piece stays connected even if any number of rows is removed from its top. The top row, the bottom row, the left column, and the right column each contain at least one wooden square.
• A line with two integers D and W (1 ≤ D ≤ 10000, 1 ≤ W ≤ 1000), the depth (number of rows) and width (number of columns) of the lock.
• D lines follow, each with exactly W characters describing the lock, using # for wood and . for empty space.

For each test case, print one line.

Depth is the distance between the bottom edge of the key and the top edge of the lock, so a key resting on top of the lock is at depth 0. If the key can be moved (using only downward and sideways moves) so that it passes completely through the lock and exits at the bottom, print:

The key can fall through.

Otherwise, let X be the maximum depth the key can reach, and print:

The key falls to depth X.