雷蒙德是查理的兄弟。他有一种计数超能力，把$246$根牙签洒在地板上，雷蒙德只是瞥了一眼就知道数量。查理很想能够做到这样的酷事。他想在类似的任务中击败他的兄弟。

这是查理所想到的。想象一下，你得到一系列$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$个相邻数字的交换进行排序。但是，甚至可以使用三个这样的交换对其进行排序：

开始于：2 8 0 3

交换（8 0）2 0 8 3

交换（2 0）0 2 8 3

交换（8 3）0 2 3 8

问题是：对给定序列进行排序的相邻数字的最小交换次数是多少？由于查理没有雷蒙德的超能力，他决定作弊。这是你进入游戏的地方。他要求你为他写一个回答这个问题的计算机程序。请放心，他会为此付出非常好的奖励。

输入格式

第一行包含方案的数量。

对于每种情况，给出一行首先包含序列的长度$N$（$1 \leq N \leq 1000$），然后是序列的$N$个元素（每个元素是[$-1000000,1000000$]中的整数）。此行中的所有数字均由单个空格分隔。

输出格式

使用包含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

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$262144\mathrm{KB}$