Ходи конем!
Ваш друг досліджує проблему обходу конем (ПОК) всіх клітинок шахової дошки, побувавши при цьому на кожному полі лише один раз. При цьому самою важкою частиною вирішення цієї проблеми, на думку Вашого друга, є підзадача знаходження довжини найкоротшого маршруту коня між двома заданими клітинками, і як тільки він її розв'яже, частину задачі, що залишиться, йому розв'язати буде досить легко. Звичайно, Вам відомо, що в дійсності це є з точністю навпаки.
Ось Ви і запропонували другу написати програму, яка розв'язує "важку" частину його задачі.
Напишіть програму, яка знаходить довжину найкоротшого маршруту коня між двома заданими клітинками a та b.
Вхідні дані
Кожен тест містить в окремому рядку координати стартового та кінцевого поля маршруту коня. Кожна координата складається з назви вертикалі у вигляді латинської літери (a - h) та номеру горизонталі у вигляді цифри (1 - 8), як це прийнято у шаховій нотації.
Вихідні дані
Для кожного тестового випадку у окремому рядку виведіть повідомлення "To get from xx to yy takes n knight moves.", де xx - стартова задана клітинка, yy - кінцева клвтинка, n - мінімальна довжина маршруту.