Problem H
Hiding Places

In chess, the knight is one of the more interesting pieces. As illustrated below, it moves by jumping two spaces up or down and one to the left or right. Alternatively, it can jump two spaces to the left or right and one space up or down. This lets the knight cover a lot of chess board in just a few moves. No matter where the knight starts out, it can eventually reach any other space.

Given a chess board with just one knight on it, you want to find the hiding places, the spaces that it would take the knight the most jumps to reach from its initial location. For example, it would take the knight at least two jumps to reach space a8 in the board above. However, it would take at least three jumps for it to reach c1. Since there are other spaces that it would take the knight even more jumps to reach, neither a8 nor c1 are among the hiding places for this initial position of the knight.

Input

Input begins with a line containing an integer $1 \le n \le 64$ indicating the number of test cases. The following $n$ lines each contain an initial location for the knight. Knight locations will be given using the common chess notation of a lowercase letter (a-h) for the file (column) followed by a number (1-8) for the rank (row). The layout of the board and rank and file labels are illustrated in the figures above.

Output

For each test case, report the number of jumps to the hiding places for the given initial location of the knight. Also report the list of hiding places using the same chess file and rank notation used in the input. If there are multiple hiding places, sort them from top to bottom and sort those in the same rank from left to right.

2
d5
a1

4 b7 f7 b3 f3 h1
6 h8