问题背景

雷蒙德·巴比特（Raymond Babbitt）让他的兄弟查理（Charlie）感到非常抓狂。最近，雷蒙德仅仅扫了一眼散落在地板上的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次相邻交换来排序。然而，实际上可以用3次这样的交换来排序：

初始序列：$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

来源

TUD Programming Contest 2003, Darmstadt, Germany