Сортування більярдних куль
Обертання — це одна з популярних ігор у більярді. У ній використовуються 15 куль, пронумерованих від 1 до 15, які розташовуються, як показано на схемі на початку гри. (Примітка: порядок куль змінено від реальних правил Обертання для спрощення задачі.)
Ви — інженер, який розробляє автоматичну машину для більярду. На першому етапі вам потрібно було створити машину, яка встановлює початкову конфігурацію. Цей проект пройшов успішно, і нарешті була створена машина, яка могла розташувати кулі у трикутній формі. Однак, на жаль, вона не могла розмістити кулі в правильному порядку.
Тепер ви намагаєтеся створити іншу машину, яка виправляє порядок куль, обмінюючи їх. Щоб зменшити витрати, дозволено лише обмінювати кулю #1 з її сусідніми кулями, які не знаходяться в тому ж рядку. Наприклад, у випадку нижче, можна обміняти лише такі пари: (1,2), (1,3), (1,8) та (1,9).
Напишіть програму, яка обчислює мінімальну кількість обмінів, необхідних для цього.
Вхідні дані
Перша строка кожного тестового випадку містить ціле число N (1 ≤ N ≤ 5), яке є кількістю рядків.
Наступні N рядків описують, як кулі розташовані першою машиною; i-й з них складається рівно з i цілих чисел, які є номерами куль.
Введення завершується, коли N = 0. Ваша програма не повинна виводити для цього випадку.
Вихідні дані
Для кожного тестового випадку виведіть номер випадку та мінімальну кількість обмінів.
Ви можете припустити, що будь-яке розташування можна виправити не більше ніж за 45 обмінів.