Efficient Algotithms 2022

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ć.

Wejście

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.

Wyjście

Dla każdego z zestawów należy wypisać w ilu najmniej krokach da się posortować karty rosnąco.

Przykładowe wejście

3
3
1 2 3
3
3 2 1
5
1 5 3 2 4

Przykładowe wyjście

0
2
2

---

When playing cards, you have probably experienced the necessity of arranging the large number of cards held in your hand in a certain order. It is not uncommon to want to do this very quickly so as to not block the game.

Consider some simple rules for sorting cards. In one turn, you can remove any (exactly one) card from the fan held in your hand and put it in any other place. Your task is, for the given order of cards in the hand at the beginning, to specify in how many least steps it can be sorted in the sorted order.

Input

The first line of input contains the number of test sets. Each set consists of two lines. The first contains the number of N (1 ≤ N ≤ 100000) cards held in hand. The second line contains a permutation of the set of numbers {1,2 ... N} that represents the order of the cards in hand at the very beginning.

Output

For each set, write out in how many least steps the cards can be sorted ascendingly.

Sample Input

3
3
1 2 3
3
3 2 1
5
1 5 3 2 4

Sample Output

0
2
2