Coalescing Continents

Continental drift is the idea that the earth's continents were once joined together as a single landmass and, over a long time, drifted apart to reach their present positions.

In this problem we study the reverse process: the coalescence of continents.

Assume the continents were originally merged into one large square. Over time that square broke into $K$ rectangular continents that drifted away from their source.

You are given the current positions of the continents (rectangles), whose outlines were traced with the help of satellites. Your first task is to decide whether the data is valid. The data is valid if you can move the rectangles so that together they form a square. In one move you may pick any single rectangle and push it one unit in one of the four directions (north, south, east, or west). While moving, continents may slide underneath one another, so more than one continent may occupy the same position at the same time. If a square can be formed, you must also report the minimum number of moves required. Where the finished square ends up does not matter. Note that in the final arrangement no two continents may overlap, and the square must be solid (it may not contain any holes).

The first line contains an integer $T$ ($T \le 200$), the number of test cases. Each test case consists of 20 lines of 20 characters. Each character is either a dot (.), representing empty space, or an x (ASCII 120). Every x belongs to some continent.

Notes:

• x characters that belong to different continents are never adjacent to each other. Every x is part of some rectangle.
• Two cells are adjacent if they share a common edge.
• There are exactly 25 x characters in each grid.
• The number of continents $K$ is at most 5.
• There is a blank line before each test case.
• The rectangles and the target square are axis-aligned.
• The world here is flat: the first and last rows are not adjacent, and neither are the first and last columns.

For each test case, print the case number first. If it is not possible to form a square by moving the rectangles, print invalid data. Otherwise, print the minimum number of moves required. Use the format shown in the examples: Case k: <answer>.