Description

Suppose you have an 8x8 chessboard and chess that move with following rules.

1. The chess can move only in the chessboard.

2. The chess can move toward one direction for two cells, and move toward another direction for three cells.

For example, if the chess is in (d,5) now, then the chess is able to reach 

(a,3),(b,2),(f,2),(g,3),(g,7),(f,8),(a,7),(b,8)

in next move. (See figure 1)

Fig 1.

You are given two coordinates of the chessboard. The first one is the start position and the second one is the target position. Your task is to determine the minimum steps required to move from the start position to the target position.

For example, given input: d1 d5, you should output 2.

Both ( d1 -> a3 -> d5 ) and ( d1 -> g3 -> d5) takes two moves. (See figure 2)

There's another path (d1 -> g3 ->e6 ->b8->d5), but it is not the shortest one. (See figure 3)

Every testcase has at least one solution

You are not allowed to use STL <queue>

Hint: 

Maintain a queue that store coordinates.

First, push the start position into the queue.

In each time step, pop an element from the queue, then check every coordinate that can arrive from the current position, if they are

not visited yet, push them into the queue.

Until the target position is reached.

 

 

Fig 2.

Fig 3.

 

 

Input

The input will contain one or more testcases. Each testcase consists of one line containing two coordinates a and b. A coordinate is represented by a letter (a,b,c,d,e,f,g,h) and a digit (1,2,3,4,5,6,7,8)

 

  

Output

For each testcase, output the minimum moves required to move from a to b. Followed by a newline character  '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss