Chess

In chess, bishop is the chessman which can only move diagonally. It is well-known that bishops can reach only fields of one color but all of them, in some number of moves (assuming that there are no other figures on the board). You are given two coordinates of a chessboard and should determine if a bishop can reach the second field from the first one and if so, then how. Coordinates in chess are given by a letter ('A' to 'H') and a number (1 to 8). The letter specifies the column (file), the number specifies the row (rank) on the chessboard.

Figure 1: Chessboard, bishop, and fields the bishop can reach in one move.

Input Specification

The input starts with the number of test cases. Each test case consists of one line, containing the start position X and the end position Y. Each position is given by two space-separated characters: a letter for the column and a number for the row. There are no duplicate test cases in one input.

Output Specification

Output one line for every test case. If it's not possible to move a bishop from X to Y in any number of moves, output “Impossible”. Otherwise, output one possible move sequence from X to Y. Output the number n of moves first (allowed to be 4 at most), followed by n + 1 positions, which describe the path the bishop has to move. The characters should be separated by single spaces. There may be many possible solutions. Any one with at most 4 moves will be accepted. Remember that in a chess move, at least one chessman (the bishop in this case) has to change its position to be a valid move (i.e., two consecutive positions in the output must differ).

Sample Input

1. 3
2. E 2 E 3
3. F 1 E 8
4. A 3 A 3

download as text file

Output for Sample Input

1. Impossible
2. 2 F 1 B 5 E 8
3. 0 A 3

download as text file