Шахи
На шахівниці розміщено дві білі тури (♖) і один чорний король (♚). Білі починають гру. Ваше завдання — граючи за білих, поставити мат чорному королю якомога швидше.
Напишіть програму, яка визначить мінімальну кількість ходів, які білі повинні виконати, щоб поставити мат чорному королю, за умови, що чорні дотримуються найкращої можливої стратегії для затягування гри.
Деяка інформація про правила шахів:
Описана вище позиція не є легальною в шахах, оскільки на дошці немає білого короля. Окрім цього, гра відбувається за правилами шахів.
Розмір дошки 8×8 клітинок. Стовпці дошки позначені літерами від a до h, а рядки цифрами від 1 до 8.
Гравці (Білі та Чорні) по черзі рухають одну фігуру свого кольору за раз. У контексті цієї задачі ми рахуємо лише ходи, зроблені Білими.
Тура рухається горизонтально або вертикально, через будь-яку кількість незайнятих клітинок. Вона не може перестрибувати або залишатися в тій самій клітинці, що й інша біла тура.
Шах — це загроза взяття короля на наступному ході, тобто позиція, в якій одна з тур знаходиться на тій самій лінії, що й король.
Король може рухатися на одну клітинку в будь-якому напрямку (горизонтально, вертикально або діагонально), якщо цей хід не поставить короля під шах. Якщо ця умова виконується, королю не заборонено зайняти клітинку, вже зайняту однією з тур. У цьому випадку тура знімається з гри.
Мат — це позиція, в якій королю загрожує взяття (тобто він під шахом) і немає жодного легального ходу для уникнення загрози.
Пат — це ситуація, коли гравець, чий хід, не під шахом, але не має жодного легального ходу. Правила шахів передбачають, що коли виникає пат, гра закінчується внічию (що неприйнятно для Білих).
Вхідні дані
Перша строка вхідних даних містить кількість позицій (яка є принаймні 1), а кожна з наступних строк містить опис однієї позиції. Усі позиції у вхідних даних різні.
Позиція представлена розташуванням трьох фігур на дошці: спочатку чорний король, а потім дві білі тури. Гарантується, що жодні дві фігури не займають одну клітинку і на початковій позиції немає шаху.
Вихідні дані
Виведіть один рядок для кожної позиції у вхідних даних. Рядок повинен містити мінімальну кількість ходів, які Білі повинні зробити, щоб гарантувати мат, починаючи з відповідної позиції. У випадку, якщо досягти мети неможливо, виведіть 0 для відповідної позиції.