一半重排

给定一个长度为 $2N$ 的排列 $P=(P_1,P_2,\cdots,P_{2N})$。

一次 重排中，需要恰好选择 $N$ 个互不相同的位置。你可以任意重新排列当前位于这些被选位置上的 $N$ 个数；未被选择的位置上的数不会改变。

你的目标是将排列排成升序，即对所有 $i$ 都满足 $P_i=i$。

求所需重排次数的最小值。

输入按以下格式从标准输入给出：

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

对于每个测试用例，在一行中输出所需重排次数的最小值。

• $1 \le T \le 1500$.
• 对每个测试用例，$2 \le N \le 3000$.
• 对每个测试用例，$P$ 是 的一个排列。