SPOJ Brasil

Watson, Crick e Wilkins receberam em 1962 o prêmio Nobel de Medicina especialmente pelo seu trabalho que resultou na descoberta da estrutura das moléculas do DNA e na sua importância na transmissão de informações entre as gerações de seres vivos. Watson e Crick publicaram na revista "Nature" em 1953 o artigo em que mostravam que a molécula de DNA apresentava uma estrutura de dupla hélice. O artigo assume enorme importância nos dias de hoje, especialmente depois dos vários avanços na área.

Muitas pesquisas têm sido feitas na área de Bioinformática ligadas à descoberta da seqüência de bases que compõem as moléculas de DNA dos vários seres vivos. Em especial, a estrutura destas moléculas tem sido usada para compor teorias de como os seres vivos evoluíram e quais têm ancestrais comuns. Acredita-se que os seres vivos presentes hoje no planeta podem descender de ancestrais comuns, sendo que as modificações nos seus respectivos DNAs são devidas a fenômenos de mutação ocorridos durante a evolução. Muitos biólogos acreditam no princípio da parcimônia, que diz que o número destas mutações deve ser o mínimo possível, uma vez que a Natureza busca, de certa forma, o caminho "mais barato" para a modificação desejada.

Sua tarefa neste problema é auxiliar os pesquisadores na tarefa de determinar se duas seqüências de DNA podem ter um ancestral comum. Considere dadas duas seqüências (podemos imaginar como seqüências de números inteiros). O seu objetivo é determinar o menor número de trocas de elementos de uma das seqüências (os elementos não precisam estar em posições adjacentes na seqüência) que leva uma das seqüências na outra. Observe que podemos considerar uma das seqüências fixa (por exemplo, em ordem crescente), dessa forma buscamos o número mínimo de tais trocas que ordena a seqüência dada.

Entrada

A primeira linha da entrada possui um inteiro T que indica o número de instâncias. A primeira linha de cada instância possui um inteiro N (1 ≤ N ≤ 10000) indicando o número de inteiros na seqüência. A segunda linha contém uma permutação dos inteiros 1, 2, .., N separados por espaço.

Saída

Para cada instância imprima uma linha contendo o número mínimo de tais trocas que ordena a seqüência dada.

Exemplo de entrada
2
5
2 3 4 5 1
5
2 1 4 5 3

Exemplo de saída
4
3