eolymp
bolt
Try our new interface for solving problems

Chess

Time limit 4 seconds
Memory limit 64 MiB

Lets recall some essential points from the standard rules of the chess. Played by two players, one is playing the white pieces, another one - black ones. The game is played on a board 8×8, columns denoted by the letters from "a" to "h" from left to right, rows by the numerals 1 to 8 upwards. Each board's square is either empty or contains a single chess piece. If a piece A (not a pawn) can move to the square, occupied by some piece B, then as a consequence of this move the piece B is captured (removed from the board). Therefore, all squares where a certain non-pawn piece can be moved are said to be "under attack" by this piece. The king is forbidden to go into any square, which is under attack by any opponent's piece. If a player made such turn that the opponent's king became under attack then this situation is called "check", then the opponent must respond in such a way, that his king after his turn wouldn't be under attack. If such move doesn't exist, it is called "checkmate".

King can move one square in any of 8 directions (left, right, forward, backward, any direction on any diagonal). The Queen can move in any of 8 directions and in any number of squares, but can't cross squares occupied by other pieces.

Suppose that there are three figures on a chess board: the white king and white queen as well as black king. Now is white's move. What the minimum number of moves is required to guarantee a checkmate? Black will do everything permissible according to the rules to avoid the checkmate.

Input data

The program should read the number (TEST_NUM70000) - the number of test blocks, then the blocks theirselves. Each test block is a separate line, containing notations of three squares, where the white king, white queen and black king are placed. Each square's notation consists of written together the column letter and line number, the three notations inside line are single-space separated.

All test blocks are guaranteed to be acceptable from the point of view of chess rules (for example, the black king isn't under attack).

Output data

Your program should print a single integer for each test block - the minimum number of moves.

Examples

Input example #1
2
a3 b3 a1
a3 e3 b1
Output example #1
1
2
Author Илья Порублёв
Source Летняя школа Севастополь 2013, Волна 1, День 2