帕特里克喜欢打棒球,但有时他会花很多时间打本垒打,以至于他的头脑开始变得模糊! Patrick 确信他在 $$$n$$$ 会话中的得分遵循身份排列(即,在第一场比赛中他获得 $$$1$$$ 分,在第二场比赛中他获得 $$$2$$$ 分,依此类推)。然而,当他查看自己的记录时,却发现所有的数字都搞混了!
定义一个特殊的交换如下:选择分数的任何子数组并排列元素,使得子数组中的任何元素都不会到达与交换之前相同的位置。例如,对 $$$[1,2,3]$$$ 执行特殊交换可以产生 $$$[3,1,2]$$$,但不能产生 $$$[3,2,1]$$$,因为 $$$2$$$ 处于相同位置。
给定 $$$n$$$ 整数的排列,请帮助帕特里克找到使排列排序所需的特殊交换的最小数量!可以证明,在给定的约束下,这个数字不会超过$$$10^{18}$$$。
数组 $$$a$$$ 是数组 $$$b$$$ 的子数组,如果 $$$a$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$b$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 给定排列的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},...,a_{n}$$$ ($$$1 \leq a_{i} \leq n$$$) — 初始排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:对排列进行排序所需的特殊交换的最小数量。
示例
输入 #1
2 5 1 2 3 4 5 7 3 2 4 5 1 6 7
输出 #1
0 2
注意
在第一个排列中,它已经排序,因此不需要交换。
可以证明,您至少需要 $$$2$$$ 交换来对第二个排列进行排序。
$$$[3, 2, 4, 5, 1, 6, 7]$$$
在范围 ($$$1, 5$$$) 上执行特殊交换
$$$[4, 1, 2, 3, 5, 6, 7]$$$
在范围 ($$$1, 4$$$) 上执行特殊交换
$$$[1, 2, 3, 4, 5, 6, 7]$$$