Chess#425
In many kinds of sports, there are different rituals to reconcile competing teams or players. These may include a handshake, a bow, or even spraying champagne. The ACM (Alliance of Chess Masters) is going to have their own ritual, a chess minigame played cooperatively by two players (rather than competitively). This game is played on a 3 \times 3 chessboard, with each player controlling two knights. The goal is for the players to move their knights from a starting position to a finishing position. Moves can be made in any order (not necessarily turn by turn). As usual, two knights cannot occupy the same square.
The starting and finishing positions are determined by the referee. It turns out that some positions are more difficult than others, and some are even unsolvable—so some chess masters may be unable to complete the ritual. Your task is to write a program that, given the starting and finishing positions, determines if the puzzle can be solved, and if so, finds the minimal number of moves required to solve it.
The first line contains the number of test cases. Each test consists of lines of symbols each. The first symbols of each line describe a row of the starting position of the board, followed by a space, then the last symbols describe the corresponding row of the ending position. The white knight is represented by the symbol , the black knight by , and an empty square by . There is a blank line between tests.
For each test, print one integer—the difficulty of the puzzle. If the puzzle is unsolvable, output .
Example 1