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