描述

给定一个由从 1 到 n 的数字组成的排列，我们总是可以通过交换数字对来得到序列 1, 2, 3, …, n 。例如，如果初始序列是 2, 3, 5, 4, 1 ，我们可以按如下方式对它们进行排序：

2 3 5 4 1

1 3 5 4 2

1 3 2 4 5

1 2 3 4 5

这里使用了三次交换。问题是，给定一个特定的排列，至少需要进行多少次交换。

输入

第一行包含一个整数 t（1 <= t <= 20），表示测试用例的数量。然后是 t 个测试用例。每个用例包含两行。第一行包含整数 n（1 <= n <= 10000），第二行给出初始排列。

输出

对于每个测试用例，输出仅为一个整数，即从初始排列得到序列 1, 2, 3, …, n 所需的最少交换次数。

输入示例：
2
3
1 2 3
5
2 3 5 4 1

输出示例：
0
3

来源

POJ 月赛——2004 年 6 月 27 日 弱人