Задачі
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}.
Вхідні дані #1
2 ACM8 002# ACM# 2008 rogp mar# prog ram#
Вихідні дані #1
17 26