#717 Half Shuffle

Statement

Statement language

A permutation $P=(P_1,P_2,\cdots,P_{2N})$ of length $2N$ is given.

In one rearrangement, choose exactly $N$ distinct positions. You may arbitrarily rearrange only the $N$ values currently placed at the chosen positions. Values at unchosen positions do not change.

Your goal is to sort the permutation so that $P_i=i$ for every $i$ .

Find the minimum possible number of rearrangements.

Input

The input is given from Standard Input in the following format:

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

Output

For each test case, print the minimum possible number of rearrangements on one line.

Constraints

$1 \le T \le 1500$ .
$2 \le N \le 3000$ for each test case.
For each test case, $P$ is a permutation of .

Subtasks

#	Score	Constraints
1	10	$N \le 3$ in every test case.
2	20	$P_i=i$ for every in every test case.

Samples

Input

4
2
3 2 1 4
3
1 4 2 5 3 6
5
9 7 4 3 8 2 5 6 10 1
6
12 1 7 10 8 9 11 5 6 3 4 2

Output

The minimum numbers of rearrangements for the four test cases are $1,2,2,3$ , respectively.