请 C++ 选手不要在本题使用万能头。

题目描述

Naeco 和 Nnelit 正在玩一个名叫 "双人成行 Plus" 的游戏。就如你所想的那样，两人在探险的过程中遇到了一个小游戏，只是这个小游戏需要一点小智慧：

假设你得到了一个由 $n$ 个数字组成的序列。目标是移动这些数字，使得最终序列是有序的。唯一允许的操作是交换两个相邻的数字。

我们来尝试一个例子:

起始序列: 2 8 0 3
交换 (2 8) 得到 8 2 0 3
交换 (2 0) 得到 8 0 2 3
交换 (2 3) 得到 8 0 3 2
交换 (8 0) 得到 0 8 3 2
交换 (8 3) 得到 0 3 8 2
交换 (8 2) 得到 0 3 2 8
交换 (3 2) 得到 0 2 3 8
交换 (3 8) 得到 0 2 8 3
交换 (8 3) 得到 0 2 3 8

所以序列 (2 8 0 3) 可以通过 $9$ 次相邻数字交换来排序。但是,也可能只需要 $3$ 次交换就能完成排序:

起始序列: 2 8 0 3
交换 (8 0) 得到 2 0 8 3
交换 (2 0) 得到 0 2 8 3
交换 (8 3) 得到 0 2 3 8

问题是：对于给定的序列，需要最少进行多少次相邻数字交换才能完成排序？谁最先回答出问题的答案，谁就能得分。

刚打完 Codeweaks 的 Naeco 发现自己智力非常低下，所以想让你帮他回答这些问题。

输入格式

第一行一个整数 $T$，代表你需要帮 Naeco 解决的问题数量。

对于第 $i$ 个问题，你会得到一行由空格分隔开的若干数字。第一个数字是序列长度 $n_i$，接着共有 $n_i$ 个数字 $a_{i, j}$，代表给定序列。

输出格式

对于第 $i$ 个问题，格式如下：

首先输出一行一个字符串 "Scenario #i:"，其中 $i$ 是从 $1$ 开始的问题编号。

然后输出一行一个整数，代表排序该序列所需的最小相邻数字交换次数。

最后，输出一个空行，代表本问题回答的结束。

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

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

数据规模与约定

对于全部的测试点，保证 $1 \leq n_i \leq 1000$，$-10 ^ 6 \leq a_{i, j} \leq 10^6$。