Train Swapping#8735
At the old railway station, you can still encounter one of the last remaining train sorters. A train sorter is a railway worker whose sole task is to rearrange train cars. Once the cars are in the correct order, the train driver only needs to sequentially deliver them to the stations for which the cargo is intended.
The name "train sorter" comes from the first person who performed this task at a station located next to a railway bridge. Instead of opening vertically, the bridge rotated around a column in the center of the river. By turning the bridge by degrees, boats could pass either to the left or to the right.
The first train sorter discovered that the bridge could hold at most two cars at a time. By rotating the bridge by degrees, the cars swapped places, allowing him to rearrange them (as a side effect, the cars then ended up facing the opposite direction, but since trains can move in any direction, this was not a problem).
Now, with almost all railway sorters extinct, the railway company aims to automate their work. Part of the program that must be developed is a procedure that determines, for a given train, the minimum number of swaps of two adjacent cars required to put the train in the correct order. Your task is to create such a program.
The first line contains the number of test cases . Each test case consists of two lines. The first line of a test case contains an integer l~(0 \le l \le 10000) — the length of the train. The second line contains a permutation of the numbers from to representing the current order of the cars. The cars must be ordered so that car comes first, then car , and so on, with car last.
For each test case, print the sentence: "Optimal train swapping takes swaps.", where is an integer representing the minimum number of swaps needed.
Example 1