절반 재배열

길이 $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$는 의 순열이다.