AlgoLiga 2018

Kiedy Adrian Monk wszedł do mieszkania świadka, od razu rzuciły mu się w oczy albumy ze zdjęciami, ponumerowane liczbami od 1 do n. Zbiory fotografii nie są ustawione na półce w porządku rosnącym, co bardzo drażni naszego bohatera. Adrian postanowił je poukładać. W każdym ruchu Monk weźmie jeden lub więcej bezpośrednio sąsiadujących ze sobą albumów i przełoży je w inne miejsce na półce. Nasz bohater może wykonać dowolną liczbę ruchów. Zakładamy, że na półce znajdują się wyłącznie tomy z fotografiami.

Odpowiedz na pytanie w ilu minimalnie ruchach Adrian Monk może uporządkować dany zbiór albumów?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10] określająca liczbę zestawów danych. W kolejnych liniach znajdują się zestawy danych.

Pierwsza linia każdego zestawu danych zawiera jedną liczbę całkowitą n ∈ [2;9] oznaczającą ilość albumów ze zdjęciami. W kolejnej linii znajduje się permutacja liczb od 1 do n określająca kolejność w jakiej tomy fotografii są ustawione na półce.

Wyjście

Na wyjściu należy wypisać minimalną liczbę ruchów jakie powinien wykonać nasz bohater, aby ustawić albumy w kolejności rosnącej.

Przykład

Wejście

1
6
6 5 4 3 2 1

Wyjście

4

Wyjaśnienie do przykładu

Monk może poukładać albumy wykonując następujące ruchy (przesuwane tomy zostały pogrubione):

• 6 5 4 3 2 1
• 5 6 4 3 2 1
• 3 2 5 6 4 1
• 3 4 1 2 5 6
• 1 2 3 4 5 6