题目描述

已知大小为 $n$ 数列 $a$ 是一个由 $1$ 到 $n$ 这 $n$ 个整数组成的一个排列（即 $1$ 到 $n$ 这 $n$ 中整数均在数列 $a$ 中出现恰好一次）。

你可以对数列进行若干步操作。每一步操作，你可以选择数列 $a$ 中一段连续的子序列并任意调整它们之间的顺序，但是你不能直接选择整个数列（也就是说你们次可以选择的连续子序列的长度必须 $\lt n$）。

举个例子，如果数列 $a = [2,1,4,5,3]$ 且我们选择调整 $a[2,4]$（即数列 $a$ 的第 $2$ 个元素到第 $4$ 个元素大小为 $3$ 的连续子序列），则调整后的数列将会变为 $a = [2,5,1,4,3]$ 或者 $a = [2,1,5,4,3]$ 等等（有好多情况）。

你的任务是计算最少需要多少步操作能够让数列 $a$ 变成升序的（即让数列 $a = [1, 2, \ldots, n]$）。

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 2000)$，表示测试数据的组数。

接下来包含 $t$ 组测试数据，每组测试数据占 $2$ 行。其中第一行包含一个整数 $n(3 \le n \le 50)$，表示数列 $a$ 的大小；第二行包含 $n$ 个整数，两两之间以一个空格分隔，表示数列 $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$ 个元素结束的连续子序列（包含第 $i$ 和第 $j$ 个元素），则：

• 在第一组测试数据中（$a = [1,3,2,4]$），只需要将 $a[2,3]$ 中的两个元素交换一下即可（变成 $a=[1,2,3,4]$）；
• 在第二组测试数据中（$a = [1,2,3]$），不需要任何操作，数列 $a$ 本身就是升序的；
• 在第三组测试数据中（$a = [2,1,4,5,3]$），可以先将 $a[1,2]$ 中的两个元素交换（变成 $a = [1,2,4,5,3]$），再将 $a[3,5]$ 中的三个元素从小到大排一下序（变成 $a=[1,2,3,4,5]$）。

数据范围

• 对于 $20\%$ 的数据，$t = 1, n \le 5$；
• 对于 $50\%$ 的数据，$t \le 20, n \le 10$；
• 对于 $80\%$ 的数据，$t \le 200, n \le 20$；
• 对于 $100\%$ 的数据，$t \le 2000, 3 \le n \le 50$。