나이트의 최소 이동 횟수

체스에서 나이트는 움직임이 가장 독특한 기물이다. 나이트는 한 방향으로 두 칸 간 다음, 그 방향과 직각으로 한 칸 더 간다. 아래 그림은 나이트가 한 번에 갈 수 있는 칸을 모두 보여 준다.

이런 이동 규칙 때문에 두 칸 사이의 최단 경로를 눈으로 세기가 쉽지 않다. 나이트가 한 칸에서 다른 칸으로 가는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하라. 체스판은 8행 8열이고, 표준 표기법에서 열은 a부터 h까지의 문자로 적는다.

입력은 두 줄이다. 첫째 줄에 나이트의 출발 칸, 둘째 줄에 도착 칸이 주어진다. 각 칸은 표준 표기법으로, a부터 h까지의 열 문자 하나 뒤에 1부터 8까지의 행 숫자 하나를 붙인 형태(e4 같은 형태)로 주어진다. 출발 칸과 도착 칸은 같을 수 있다.

나이트가 출발 칸에서 도착 칸까지 가는 데 필요한 최소 이동 횟수를 정수 하나로 출력한다.