Мифические шахматы
Ваш друг Вася занимается разработкой компьютерной игры «Мифические шахматы». Он не укладывается в установленные сроки сдачи проекта.
Вася обратился к друзьям за помощью. Ему необходим модуль, вычисляющий оптимальные пути перемещения фигур из одной клетки в другую. Так как друзей у Васи много, то каждому досталась маленькая подзадача. Вам требуется написать программу, определяющую минимальное количество ходов, необходимое кентавру, чтобы добраться из одной клетки в другую.
В мифические шахматы играют на шахматной доске размером 9х9, угловые клетки которой окрашены в черный цвет. Кентавр – фигура мифических шахмат, объединяющая в себе свойства коня и слона. Когда кентавр стоит на белой клетке, он может ходить только как конь, а когда на черной – только как слон. На рисунках приведены варианты ходов для двух кентавров (буквой "K" отмечено местоположение кентавра, а звездочками – клетки, куда кентавр может сделать ход).
Входные данные
Во входном файле в первой строке записано натуральное число N – количество тестов. В следующих N строках для каждого теста записаны координаты (большая латинская буква и цифра) двух клеток доски для мифических шахмат, разделенных пробелом.
Выходные данные
Для каждого теста выводится строка, содержащая минимальное число ходов, необходимое кентавру, чтобы добраться из первой клетки во вторую. Если добраться невозможно, то выводится число "-1" (без кавычек).