B. Сортировка перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a$$$ состоящая из $$$n$$$ чисел $$$1$$$, $$$2$$$, ..., $$$n$$$ (перестановка — это массив, в котором каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Вы можете выполнять операцию следующего вида — выбрать подмассив (непрерывный подотрезок) $$$a$$$ и переставить в нем элементы произвольным образом. Но такую операцию нельзя применить ко всему массиву целиком.

Например, $$$a = [2, 1, 4, 5, 3]$$$ и мы хотим применить операцию к подмассиву $$$a[2, 4]$$$ (подмассиву, содержащему все элементы от $$$2$$$-го до $$$4$$$-го), тогда после операции массив может иметь вид $$$a = [2, 5, 1, 4, 3]$$$, или, например, $$$a = [2, 1, 5, 4, 3]$$$.

Ваша задача — определить минимальное количество вышеописанных операций, позволяющих отсортировать перестановку $$$a$$$ в возрастающем порядке.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных.

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 50$$$) — количество элементов в перестановке.

Вторая строка набора входных данных содержит $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — заданную перестановку $$$a$$$.

Выходные данные

Для каждого набора выходных данных выведите одно целое число — минимальное количество вышеописанных операций, позволяющих отсортировать перестановку $$$a$$$ по возрастанию.

Пример
Входные данные
3
4
1 3 2 4
3
1 2 3
5
2 1 4 5 3
Выходные данные
1
0
2
Примечание

В объяснениях $$$a[i, j]$$$ означает подмассив $$$a$$$, который начинается с $$$i$$$-го элемента и заканчивается $$$j$$$-м элементом.

В первом наборе входных данных из условия можно выбрать подмассив $$$a[2, 3]$$$ и поменять в нем элементы местами.

Во втором наборе входных данных перестановка уже отсортирована, поэтому операции применять не нужно.

В третьем наборе входных данных можно выбрать подмассив $$$a[3, 5]$$$ и превратить $$$a$$$ в $$$[2, 1, 3, 4, 5]$$$, а затем выбрать подмассив $$$a[1, 2]$$$ и превратить $$$a$$$ в $$$[1, 2, 3, 4, 5]$$$.