Phoebe's knights, being as weird as herself, can move with some different patterns too!

As in our chess, Knight's move is: 2 steps in a direction then 1 step in any of the two possible perpendicular directions.

But Phoebe's Knight are sometimes even more energetic that they can move N steps in a direction then 1 perpendicular turn.

as shown above, For N=4 here knight from C5 can take 4 possible moves, ("Xs").

Now you are given an N and 2 positions (Initial and final) of Knight, you have to find the minimum number of moves required to go from initial to final position.

Input:

 First line containing an integer T, the number of test cases.
 Each test case consists of two lines, first with N. 
 And second showing two space separated positions in the form XD.
 (where X can be a lowercase letter from 'a' to ' h' and D can be a digit from 1 to 8).

Output:

 For each test case, output the required answer(Minimum moves required), in a newline. 
 If it's impossible print "-1" (without quotes).

Constraints

 0<T< 5000
 0<N<8
 'a' <= X <= 'h'
 1<=D<=8