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