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