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