给你一个排列 $$$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$$$) — 排列中的元素数量。
测试用例的第二行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 - 给定的排列 $$$a$$$。
输出
对于每个测试用例,输出一个整数 - 如上所述对数组 $$$a$$$ 按升序排序的最少操作数。
示例
输入 #1
3 4 1 3 2 4 3 1 2 3 5 2 1 4 5 3
输出 #1
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]$$$。