题目描述

你醒啦？现在是周日的早上十三点（？）。睡意朦胧的你想起来，睡前还在跟舍友玩 "双人成行"。平行世界的 "双人成行" 中包含一个数字排序的小游戏：

在你面前的，是 $n$ 个摆成一条直线的石头，每个石头上有一个数字。游戏的目标是通过交换 相邻 的石头，使得由数字组成的序列非降序，并 最小化 交换次数。

你依稀记得，上床之前，舍友三下五除二轻松完成了这个游戏，但不怀好意的他把石头重新打乱了！鉴于舍友已经去上课了，你决定自己完成这个游戏。

输入格式

输入的第一行包含一个整数 $t$，代表测试用例的数量。对于每组测试用例：

第一行包含一个整数 $n$，代表石头的数量。

第二行包含 $n$ 个整数 $a_i$，代表第 $i$ 个石头上的数字。

输出格式

对于每组测试用例，输出一个整数，代表使得序列非降序的所需的最小交换次数。

4
4
2 8 0 3
10
0 1 2 3 4 5 6 7 8 9
6
-42 23 6 28 -100 65537
5
0 0 0 0 0

3
0
5
0

说明

对于样例 $1$，可能的一种交换方式为：

1. 交换 $8$ 和 $0$，得到 $2, 0, 8, 3$；
2. 交换 $2$ 和 $0$，得到 $0, 2, 8, 3$；
3. 交换 $8$ 和 $3$，得到 $0, 2, 3, 8$

可以证明没有更少的交换次数。

数据规模与约定

对于全部的测试点，保证 $1 \leq t \leq 1000$，$1 \leq n \leq 1000$，$-10 ^ 6 \leq a_i \leq 10^6$，$n$ 的总和不超过 $10 ^ 4$。

本题改编自 POJ P1804