Шахматы
Во многих видах спортивных соревнований имеются различные ритуалы, направленные для примирения конкурирующих команд или игроков. Это может быть рукопожатие, поклон или даже разбрызгивание шампанского. ACM (Alliance of Chess Masters) собирается создать свой собственный ритуал, шахматную миниигру, в которой участвует два игрока в союзе друг с другом (а не как обычно, друг против друга). Игра проходит на шахматной доске размером 3x3, у каждого из игроков имеется два шахматных коня, которых они должны переместить так, чтобы добраться от одной позиции до другой (игроки могут делать шаги в любом порядке, не обязательно по очереди). При этом два коня не могут занимать одну и ту же клетку.
Стартовое и завершающее положения определены судьей. Оказывается, что некоторые такие задачи являются более трудными, чем другие, а некоторые могут быть даже неразрешимыми - поэтому, некоторые игроки иногда неспособны закончить ритуал. Ваша задача состоит в том, чтобы написать программу, которая по заданным положениям начальной и конечной расстановки, сможет определить возможность успешного окончания игры, а в случае успеха сможет так же определить сложность задачи – минимально возможное количество ходов, необходимых для разрешения данной задачи.
Входные данные
Состоит из нескольких тестов, в каждом из которых 3 строки по 7 символов в каждой. Первые 3 символа каждой строки описывают соответствующую строку шахматной строки для начальной позиции, затем идет пробел и замыкающие 3 символа, описывающие аналогичным образом строку конечной позиции. Белый конь обозначается символом «W», а черный – символом «B», пустые клетки помечаются «.» (точка). Тестовые случаи отделены друг от друга пустой строкой. Количество тестов указано в первой строке.
Выходные данные
Для каждого теста выведите одно целое число – сложность задачи. Если задача не имеет решения, то вывести -1.