CF1525B.Permutation Sort

You are given a permutation $a$ consisting of $n$ numbers $1$, $2$, ..., $n$ (a permutation is an array in which each element from $1$ to $n$ occurs exactly once).

You can perform the following operation: choose some subarray (contiguous subsegment) of $a$ and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array.

For example, if $a = [2, 1, 4, 5, 3]$ and we want to apply the operation to the subarray $a[2, 4]$ (the subarray containing all elements from the $2$-nd to the $4$-th), then after the operation, the array can become $a = [2, 5, 1, 4, 3]$ or, for example, $a = [2, 1, 5, 4, 3]$.

Your task is to calculate the minimum number of operations described above to sort the permutation $a$ in ascending order.

给你一个由 $n$ 个数 $1, 2, \dots, n$ 构成的排列 $a$（排列是指每个从 $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$ 升序排序所需的上述操作的最少次数。

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The first line of the test case contains a single integer $n$ ($3 \le n \le 50$) — the number of elements in the permutation.

The second line of the test case contains $n$ distinct integers from $1$ to $n$ — the given permutation $a$.

第一行包含一个整数 $t$（$1 \le t \le 2000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 50$）—— 排列中元素的个数。

每个测试用例的第二行包含 $n$ 个互不相同的整数，取值范围为 $1$ 到 $n$ —— 给定的排列 $a$。

For each test case, output a single integer — the minimum number of operations described above to sort the array $a$ in ascending order.

对于每个测试用例，输出一个整数——即按上述描述对数组 $a$ 进行升序排序所需的最少操作次数。

In the explanations, $a[i, j]$ defines the subarray of $a$ that starts from the $i$-th element and ends with the $j$-th element.

In the first test case of the example, you can select the subarray $a[2, 3]$ and swap the elements in it.

In the second test case of the example, the permutation is already sorted, so you don't need to apply any operations.

In the third test case of the example, you can select the subarray $a[3, 5]$ and reorder the elements in it so $a$ becomes $[2, 1, 3, 4, 5]$, and then select the subarray $a[1, 2]$ and swap the elements in it, so $a$ becomes $[1, 2, 3, 4, 5]$.

在解释中，$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]$。