Swamp Kangaroo

Kangaroos are fascinating creatures. For one, carrying their offspring in a pouch is very cute, and it reminds us of our own ways of transporting babies. For another, they can jump really far. That is quite useful — in particular if you are a kangaroo stuck in a swamp with only small islands of land and crocodiles swimming around, since you would rather not land in the water. Besides raw jumping strength, it also helps to have some computational power to work out exactly how to use that strength to get where you need to go. That is where your programming friends come in.

We model kangaroo movement as follows. A kangaroo can only move North–South or East–West; no other directions (such as diagonals) are allowed. In a single hop the kangaroo can jump any integer distance between $1$ and $5$, and each hop takes one unit of time. After a longer jump, however, it must rest before jumping again: after jumping a distance $d$, the kangaroo has to rest $(d-1)^2$ units of time before it can jump again. In addition, if the next jump is in a different direction from the previous one, the kangaroo needs one extra unit of time between the two jumps to turn around.

The swamp is described by a two-dimensional grid. Each cell is either water, written as a dot ., or land, written as X. Two cells are marked specially: K is the kangaroo's starting position and G is the goal it wants to reach (both are of course land). A jump may pass over water, but the kangaroo must land on a land cell that lies inside the grid. Find the shortest time in which the kangaroo can reach the goal, if it can reach it at all. It does not matter whether the kangaroo is tired when it arrives; it does not have to rest upon arrival.

The first line contains the number of data sets $K$. Each of the following data sets has this form: the first line contains two integers $h$ and $w$ ($1 \le h, w \le 30$), the height and width of the swamp map. The next $h$ lines each contain exactly $w$ characters, where every character is ., X, K, or G. Together these $h \times w$ characters describe the swamp. Each data set contains exactly one K and exactly one G.

For each data set, print a line containing Data Set x:, where x is the data set's number (starting from $1$). On the following line print the minimum amount of time in which the kangaroo can reach the goal, or Impossible if the goal cannot be reached. Print a blank line between consecutive data sets.