Шахи
Нагадаємо деякі важливі правила гри в шахи, які знадобляться для цього завдання. Грають два гравці: один грає білими фігурами, інший — чорними. Гра відбувається на дошці розміром 8x8. Стовпчики позначаються літерами від "a" до "h" зліва направо, а рядки — цифрами від 1 до 8 знизу вгору. Кожна клітинка дошки або порожня, або містить одну фігуру. Якщо фігура A (не пішак) може походити згідно з правилами на клітинку, зайняту чужою фігурою B, то внаслідок такого ходу фігуру B знімають з дошки. Тому всі клітинки, куди фігура може походити, вважаються "під боєм" цієї фігури. Королю заборонено ходити в клітинку, яка знаходиться під боєм будь-якої чужої фігури. Якщо один з гравців зробив хід, внаслідок якого король противника опинився під боєм (це називається "шах"), противник зобов'язаний відповісти таким чином, щоб його король більше не був під боєм. Якщо такого ходу не існує, це називається "мат".
Король може ходити на одну клітинку в будь-якому з 8 напрямків (вліво, вправо, вперед, назад, або по діагоналі). Ферзь може ходити в будь-якому з 8 напрямків на будь-яку кількість клітинок, але не може перестрибувати через інші фігури.
На шаховій дошці знаходяться три фігури: білий король, білий ферзь і чорний король. Зараз хід білих. Яка мінімальна кількість ходів потрібна, щоб вони гарантовано поставили мат? Чорні будуть робити все можливе, щоб уникнути мата, дотримуючись правил гри.
Вхідні дані
Програма повинна прочитати число TEST_NUM — кількість тестових випадків, а потім самі тестові випадки. Кожен тестовий випадок — це окремий рядок, в якому вказані три позначення клітинок, де знаходяться білий король, білий ферзь і чорний король відповідно, розділені пробілом (позначення клітинки складається з літери стовпця і номера рядка).
Всі задані позиції гарантовано допустимі з точки зору шахових правил (наприклад, чорний король не знаходиться під боєм).
Вихідні дані
Ваша програма повинна вивести для кожного тесту єдине число — мінімальну кількість ходів.