Шахи#425
У багатьох видах спортивних змагань існують різноманітні ритуали для примирення конкуруючих команд або гравців. Це може бути рукостискання, уклін або навіть розбризкування шампанського. ACM (Альянс майстрів шахів) вирішує провести власний ритуал — шахову мінігру, у якій двоє гравців працюють разом (а не змагаються один проти одного). Гра відбувається на шаховій дошці розміром 3 \times 3, кожен гравець керує двома конями. Мета — пересунути коней із початкової позиції у кінцеву. Ходи можна робити у довільному порядку (не обов'язково по черзі). Два коні не можуть стояти на одній клітинці водночас.
Початкову і кінцеву позиції визначає суддя. Деякі задачі складніші за інші, а деякі можуть бути зовсім нерозв’язними — іноді шахові майстри не зможуть пройти ритуал. Ваше завдання — написати програму, яка за початковою та кінцевою позиціями визначить, чи можливо розв'язати задачу, а якщо можливо — обчислить мінімальну кількість ходів для цього.
У першому рядку вказано кількість тестів. Кожен тест складається з рядків по символів. Перші символи описують рядок початкової позиції, за якими йде пропуск, після якого ще символи — рядок кінцевої позиції. Білий кінь позначається символом , чорний — , а порожня клітинка — точкою . Тести відокремлені порожнім рядком.
Для кожного тесту виведіть одне ціле число — складність задачі. Якщо задача не має розв’язку, виведіть .
Приклад 1