题目描述

给定一个由 $n$ 个数 $1, 2, \ldots, 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$ 排成升序所需的最少操作次数。

输入格式

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

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

每个测试用例的第二行包含 $n$ 个互不相同的整数，表示给定的排列 $a$，这些整数是 $1$ 到 $n$ 的一个排列。

输出格式

对于每个测试用例，输出一个整数，表示将数组 $a$ 排成升序所需的最少操作次数。

说明/提示

在解释中，$a[i, j]$ 表示从第 $i$ 个元素到第 $j$ 个元素的子数组。

在第一个样例中，你可以选择子数组 $a[2, 3]$ 并交换其中的元素。

在第二个样例中，排列已经有序，因此不需要进行任何操作。

在第三个样例中，你可以选择子数组 $a[3, 5]$ 并重新排列其中的元素，使 $a$ 变为 $[2, 1, 3, 4, 5]$，然后选择子数组 $a[1, 2]$ 并交换其中的元素，使 $a$ 变为 $[1, 2, 3, 4, 5]$。

由 ChatGPT 4.1 翻译

样例

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

1
0
2