11.02 Старшая лига

Mythical Chess

prb498Your friend Vasya is developing a computer game "Mythical Chess". He does not fit within the established project timeframe.

Vasya turned to friends for help. It needs a module that calculates the best way to move pieces from one cell to another. Since friends Vasja much, everyone went to a small subproblem. You need to write a program that defines the minimum number of moves required centaur to get from one cell to another.

In the mythical play chess on the chessboard the size9х9, angular cells which are painted in black. Centaur - mythical figure of chess, combining the properties of the horse and elephant. When the centaur is a white box, he could only walk like a horse, and when the black - just like an elephant. Figures are variants of moves for the two centaurs (the letter "K" marked the location of a centaur, and asterisks - cells, where the Centaur can make a move).


In the input file is written in the first line of natural numberNthe number of tests. In the nextNlines for each test recorded the coordinates (large letters and numbers) of two cell boards for the mythical chess, separated by a space.


For each test displays a string containing the minimum number of moves required centaur to get from the first cell in the second. If you can not reach, then displays the number of "-1" (without the quotes).

Time limit 1 second
Memory limit 64 MiB
Input example #1
H6 E5
A6 F6
Output example #1