Рабочее место участника

In many kinds of sports, there are different rituals to reconcile competing teams or players. It may be handshake, bow or even spraying of champagne. The ACM (Alliance of Chess Masters) is going to have their own ritual, chess minigame, played by two players cooperatively (instead of competitively). They have 3x3 chess board, with each player having two knights, and players move their knights to get from starting position to finishing position (moves are made not turn by turn, but in any order). As usual, two knights cannot occupy same square.

Starting and finishing position are determined by referee; and it turned out that some positions are more difficult than others, and some even unsolvable – therefore some chess masters would be unable to complete the ritual. Your task is to write a program, which, given starting and finishing positions, rules out whether board can be solved, and determines the difficulty of the position, measured in minimal number of moves required to get from staring position to finishing.

The first line contains the number of test cases. Each test has 3 lines 7 symbols each: 3 symbols describe line of the board starting position, space, 3 symbols describe line of the board ending position. White knight is represented by capital letter 'W', black knight is represented by capital 'B', and empty square is represented by a dot '.' There is a blank line between tests.

For each test, a line contains difficulty of position. If position is unsolvable, output `-1`.

2
WBB ..W
W.. ..W
... .BB

..B ..B
W.B ..B
W.. WW.

4
-1