Problems
Jammed
Jammed
Всем известна игра \textbf{15}, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от \textbf{1} до \textbf{15} в квадрате \textbf{4}×\textbf{4}. На основе данной игры была разработана другая -- поле в ней лишь \textbf{4}×\textbf{2} клетки, на поле \textbf{7} фишек, но на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке -- один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя -- упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов.
Свободная клетка обозначается специальным символом \textbf{#} и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ \textbf{0} можно переместить вниз на свободную клетку, тогда \textbf{0} будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву \textbf{C} или цифру \textbf{2}.
\includegraphics{https://static.e-olymp.com/content/ab/abfc9ad650c4b0adde50f563e5769f8b296f99eb.jpg}
\InputFile
Первая строка содержит количество тестов (не больше \textbf{100}). Далее в каждом тесте содержится четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две - образец. Каждая строка содержит \textbf{4} символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом \textbf{#}. Тесты разделены между собой пустой строкой.
\OutputFile
Для каждого теста в выходной файл выводится строка, содержащая минимальное количество перемещений, необходимых для получения искомой комбинации. Если нужную комбинацию получить нельзя, выведите число \textbf{-1}.
Input example #1
2 ACM8 002# ACM# 2008 rogp mar# prog ram#
Output example #1
17 26