Grając w karty pewnie zetknąłeś się z koniecznością ułożenia
w pewnej kolejejności dużej liczby kart trzymanych w ręku. Nierzadko trzeba
to zrobić bardzo szybko, żeby nie blokować gry.
Rozważmy pewne uproszczone zasady sortowania kart. W jednym korku możemy
wyciągnąć dowolną (dokładnie jedną) kartę z wachlarza trzymanego w ręce i włożyć
ją w dowolne inne miejsce. Twoim zadaniem jest dla zadanej kolejności kart
w wachlarzu, który trzymasz na pocztąku, podać w ilu najmniej krokach można
go posortować.
Pierwszy wiersz wejścia zawiera liczbę zestawów testowych. Każdy zestaw składa się z dwóch wierszy. Pierwszy zawiera liczbę kart N (1 ≤ N ≤ 1000) trzymanych w ręce. Drugi wiersz zawiera permutację zbioru liczb {1,2,...,N}, który reprezentuje kolejność kart w wachlarzu, jaki trzymamy na pocztąku.
Dla każdego z zestawów należy wypisać w ilu najmniej krokach da się posortować karty rosnąco.
3 3 1 2 3 3 3 2 1 5 1 5 3 2 4
0 2 2