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