Сортувальник поїзда
На старій залізничній станції ви ще можете зустріти одного з останніх "сортувальників поїздів". Сортувальник поїзда — це працівник залізниці, чиє єдине завдання полягає в перестановці вагонів поїздів. Коли вагони розташовані у правильному порядку, машиністу залишається лише відчепити їх по черзі на станціях, для яких призначено вантаж.
Назва "сортувальник поїзда" походить від першої людини, яка виконала це завдання на станції, розташованій біля залізничного мосту. Замість вертикального відкриття міст обертався навколо колони в центрі річки. Повернувши міст на 90 градусів, човни могли пройти вліво або вправо.
Перший сортувальник поїзда виявив, що міст може вміщувати максимум два вагони. Повернувши міст на 180 градусів, вагони мінялися місцями, що дозволяло йому переставляти вагони (як побічний ефект, вагони потім рухалися в протилежному напрямку, але вагони поїзда можуть рухатися в будь-якому напрямку, тож це не мало значення).
Тепер, коли майже всі залізничні сортувальники зникли, залізнична компанія хоче автоматизувати їхню роботу. Частина програми, яку потрібно розробити, — це процедура, що визначає для даного поїзда мінімальну кількість перестановок місцями двох суміжних вагонів, необхідних для впорядкування поїзда. Ваше завдання — створити таку програму.
Вхідні дані
Перший рядок містить кількість тестів n. Кожен тест складається з двох рядків. Перший рядок тесту містить ціле число l (0 ≤ l ≤ 10000), що визначає довжину поїзда. Другий рядок тесту містить перестановку чисел від 1 до l, що вказують на поточний порядок вагонів. Вагони повинні бути упорядковані так, щоб вагон 1 йшов першим, потім вагон 2, і так далі. Вагон номер l повинен йти останнім.
Вихідні дані
Для кожного тесту виведіть речення: "Optimal train swapping takes s swaps.", де s - ціле число.