The Game

One morning you wake up and think: "I am such a good programmer. Why not make some money?" So you decide to write a computer game.

The game takes place on a rectangular board of $w \times h$ squares. Each square may or may not contain a game piece.

An important part of the game is deciding whether two game pieces can be connected by a path that satisfies both of the following properties:

1. It consists of straight segments, each one either horizontal or vertical.
2. It does not cross any other game piece.

The path is allowed to leave the board temporarily.

For example, two pieces can be connected when some orthogonal path between them avoids every other piece, and they cannot be connected when every such path is forced to cross at least one other piece.

The part you have to write now decides whether two given game pieces can be connected under the rules above and, if so, the minimum number of straight segments needed.

The input contains descriptions of several different game situations.

The first line of each description contains two integers $w$ and $h$ ($1 \le w, h \le 75$), the width and the height of the board. The next $h$ lines describe the contents of the board; each of these lines contains exactly $w$ characters: an X where there is a game piece, and a space where there is none.

Each board description is followed by several lines containing four integers $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 \le w$, $1 \le y_1, y_2 \le h$), the coordinates of two game pieces. The upper-left corner has coordinates $(1, 1)$. The two game pieces are always different, and both squares contain a game piece. The list of piece pairs for a board is terminated by a line containing 0 0 0 0.

The whole input is terminated by a game situation with $w = h = 0$; this situation is not processed.

For each board, first output the line Board #n:, where $n$ is the number of the board (counting from 1). Then output one line for each pair of game pieces of that board. Each such line starts with Pair m: , where $m$ is the number of the pair (restarting from 1 for every board). Follow it by k segments., where $k$ is the minimum number of straight segments of a path connecting the two pieces, or by impossible. if the two pieces cannot be connected as described.

Print one blank line between the outputs of two consecutive boards.