URI Online Judge | 1382

Elementary, my Dear Watson!

By Wanderley Guimarães, IME-USP Brazil
Timelimit: 2

Watson, Crick and Wilkins received the 1962 Nobel Prize in Medicine especially for their work that resulted in the discovery of the structure of DNA molecules and their importance in the transmission of information between generations of living beings. Watson and Crick published in the journal "Nature" in 1953 an article showing that the DNA molecule had a double helix structure. The article has an immense importance these days, especially after the many advances in the field.

A lot of researches have been made in the Bioinformatics field linked to the discovery of the sequence of bases comprising the DNA molecules of various living beings. In particular, the structure of these molecules has been used to form theories of how living organisms have evolved, and which has common ancestors. It is believed that living beings present on the planet today may be descended from common ancestors, and the changes in their respective DNAs are due to phenomena of mutation occurred during evolution. Many biologists believe in the principle of parsimony, which says that the number of these mutations should be the minimum possible, since the Nature searches, somehow, the "cheaper" way for the desired modification.

Your task in this problem is to assist researchers in the task of determining whether two DNA sequences may have a common ancestor. Consider two given sequences (we can imagine as sequences of integers). Your goal is determine the smallest number of swaps of elements of one sequence (the elements don’t need be in adjacent positions in the sequence) which takes one of the sequences in the other. Note that we can consider a sequence as fixed (eg., in ascending order), thus we look for the minimum number of such swaps that orders the given sequence.


The input is composed of several test cases. The first line of input contains an integer T indicating the number of test cases. The first line of each instance has an integer N (1 ≤ N ≤ 10000) indicating the number of integers in the sequence. The second line contains a permutation of integers 1, 2, ... , N separated by a space.


For each instance print a line containing the minimum number of such swaps that sorts the given sequence.

Sample Input Sample Output

2 3 4 5 1
2 1 4 5 3