Jammed
Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4×4. На основе данной игры была разработана другая – поле в ней лишь 4×2 клетки, на поле 7 фишек, но на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов.
Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.
Входные данные
Первая строка содержит количество тестов (не больше 100). Далее в каждом тесте содержится четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две - образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #. Тесты разделены между собой пустой строкой.
Выходные данные
Для каждого теста в выходной файл выводится строка, содержащая минимальное количество перемещений, необходимых для получения искомой комбинации. Если нужную комбинацию получить нельзя, выведите число -1.