You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有连续的 2n 张椅子排成一排。有 n 对情侣坐在这 2n 个位置上。我们想通过最少的换位，使得每对情侣都坐在一起。每次换位，能交换两个人的位置。 座位的编号是 $0～2n-1$。情侣的编号也是 $0～2n-1$ ，其中 $0$ 和 $1$ 是一对，$2$ 和 $3$ 是一对，以此类推，最后一对情侣编号为 $2n-2$ , $2n-1$ 。 给出一开始第 $i$ 个位置上坐的人的编号 $row_i$ 。 求最少需要交换多少次，才能使得每对情侣坐在一起。

输入格式

多组数据。第一行一个整数 $t$ 表示数据组数。每组数据占两行，其中：

第一行一个整数 $n$，代表情侣的对数。 第二行 $2n$ 个整数，分别代表坐在第 $i$ 个位置上的人的编号。

输出格式

一个整数，代表最少需要的交换次数。

样例输入1

2
2
0 2 1 3
2
3 2 0 1

样例输出1

1
0

样例解释1

第一组数据交换人1和2的位置。第二组数据2在3的旁边，1在2的旁边，不需要交换。

数据范围

$30\%, n\leq 5$

$50\%, n\leq 10$

$100\%, n\leq 20, t\leq 3$