eolymp
Змагання

11.02 Старшая лига

Міфічні шахи

prb498Ваш друг Вася займається розробкою комп'ютерної гри «Міфічні шахи». Він не вкладається у відведені терімни здачі проекту.

Вася звернувся до друзів за допомогою. Йому потрбний модуль, який обраховує оптимальні шляхи переміщення фігур з однієї клітинки в іншу. Так як друзів у Васі багато, то кожному дісталась маленька підзадача. Вам потрібно написати програму, яка визначає мінімальну кількість ходів, потрібних кентавру, щоб дістатись з однієї клітинки в іншу.

В міфічні шахи грають на шаховій дошці розміром 9х9, кутові клітинки якої зафарбовані в чорний колір. Кентавр – фігура міфічних шахів, яка об'єднує в собі властивості коня і слона. Коли кентавр стоїть на білій клітинці, він може ходити лише як кінь, а коли на чорній – лише як слон. На рисунках приведені варіанти ходів для двох кентаврів (літерою "K" відмічено місцезнаходження кентавра, а зірочками – клітинки, кудт кентавр може зробити хід).

Вхідні дані

У вхідному файлі у першому рядку записано натуральне число N – кількість тестів. У наступних N рядках для кожного теста записані координати (велика латинськая літера і цифра) двох клітин дошки для міфічних шахів, відокремлених пропуском.

Вихіді дані

Для кожного теста виводиться рядок, що містить мінимальне число ходів, необхідних кентавру, щоб дістатись з першої клітини у другу. Якщо дістатись неможливо, то виводиться число "-1" (без лапок).

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
H6 E5
A6 F6
Вихідні дані #1
2
3