1756. Головоломка

Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4x4. На основе данной игры была разработана другая – поле в ней лишь 4x2 клетки, на поле 7 фишек, но на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов.

Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.

M 0 0 A
8 C # 2

Первая строка содержит количество тестов (не больше 100). Далее в каждом тесте содержится четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две – образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #. Тесты разделены между собой пустой строкой.

Для каждого теста в выходной файл выводится строка, содержащая минимальное количество перемещений, необходимых для получения искомой комбинации. Если нужную комбинацию получить нельзя, выведите число `-1`.

2
ACM8
002#
ACM#
2008

rogp
mar#
prog
ram#

17
26