Theta Puzzle
Головоломка Тета складається з основи, що має 6 позицій на вершинах правильного шестикутника та одну позицію в центрі, з'єднаних, як показано на рисунку нижче. У вас є шість фішок з мітками A, B, C, D, E та F. Один хід у головоломці полягає в переміщенні фішки на сусідню порожню позицію (по дозволеному з'єднанню — відрізки на діаграмі нижче). Завдання головоломки полягає в тому, щоб почати з початкового розташування фішок з порожнім центром і, за допомогою послідовності ходів, досягти конфігурації, показаної на рисунку нижче.
Початкова позиція головоломки задається перестановкою літер від A до F. Перша літера відповідає позиції A на рисунку, наступна — B, і так далі.
Послідовність ходів задається шляхом перерахування міток фішок, які потрібно перемістити, у порядку, в якому їх слід переміщати.
Наприклад, щоб розв'язати головоломку з перестановкою FACDBE, використовуйте ходи BEFAB.
Примітка: Не всі початкові перестановки можуть бути розв'язані.
Напишіть програму, яка, отримавши початкову перестановку, або знаходить найкоротшу послідовність ходів для розв'язання головоломки, або визначає, що рішення немає.
Вхідні дані
Перший рядок вхідних даних містить одне ціле число P, (1 ≤ P ≤ 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних — це один рядок, що містить номер набору даних, за яким слідує пробіл, а потім перестановка літер від A до F, що задає початкову позицію головоломки.
Вихідні дані
Для кожного набору даних є один рядок вихідних даних. Якщо рішення немає, рядок містить номер набору даних, за яким слідує один пробіл, а потім рядок NO SOLUTION. Якщо є рішення, рядок містить номер набору даних, за яким слідує один пробіл, потім кількість ходів у рішенні, за яким слідує один пробіл, а потім рішення у вигляді рядка літер від A до F. Якщо кількість ходів дорівнює нулю (0), ви все одно повинні вивести пробіл після 0, навіть якщо рядка літер немає.