나이트의 이동

당신의 친구는 순회하는 나이트 문제(Traveling Knight Problem, TKP) 를 연구하고 있습니다. 이 문제는 체스판 위에 주어진 $n$개의 칸을 나이트가 각각 정확히 한 번씩 방문하고 다시 출발점으로 돌아오는, 가장 짧은 닫힌 순회 경로를 찾는 것입니다. 친구는 이 문제에서 가장 어려운 부분이 두 칸 사이를 오가는 나이트의 최소 이동 횟수를 구하는 것이며, 그것만 해결하면 순회 경로를 찾는 일은 쉽다고 생각합니다.

물론 당신은 사실이 그 반대임을 알고 있습니다. 그래서 친구에게 그 "어려운" 부분을 대신 풀어 주는 프로그램을 작성해 주겠다고 제안합니다.

당신이 할 일은 두 칸 $a$와 $b$를 입력받아, $a$에서 $b$까지 이동하는 나이트의 최단 경로 이동 횟수를 구하는 프로그램을 작성하는 것입니다.

입력에는 하나 이상의 테스트 케이스가 주어집니다. 각 테스트 케이스는 공백 하나로 구분된 두 칸으로 이루어진 한 줄입니다. 한 칸은 체스판의 열을 나타내는 문자(a–h)와 행을 나타내는 숫자(1–8)로 이루어진 문자열입니다. 입력은 파일의 끝(EOF)까지 계속됩니다.

각 테스트 케이스마다 "To get from xx to yy takes n knight moves." 형식으로 한 줄을 출력합니다. 여기서 xx 는 출발 칸, yy 는 도착 칸, n 은 최소 이동 횟수입니다. 출력 문장은 위에 적힌 영어 형식 그대로 출력해야 합니다.