半分並べ替え

長さ $2N$ の順列 $P=(P_1,P_2,\cdots,P_{2N})$ が与えられる。

1 回の 並べ替えでは、相異なる位置をちょうど $N$ 個選ぶ。選んだ位置に現在置かれている $N$ 個の値だけを、好きな順序に並べ替えることができる。選ばなかった位置の値は変化しない。

すべての $i$ について $P_i=i$ となるように順列を昇順に整列したい。

必要な並べ替え回数の最小値を求めよ。

入力は次の形式で標準入力から与えられる。

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

各テストケースについて、必要な並べ替え回数の最小値を 1 行に出力せよ。

• $1 \le T \le 1500$.
• 各テストケースについて $2 \le N \le 3000$.
• 各テストケースの $P$ は の順列である。