背景：

雷蒙德·巴比特让他的弟弟查理发疯。最近,雷蒙德只是一瞥就数出了地上散落的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 <= N <= 1000)，然后是 N 个元素 (每个元素是一个 [-1000000, 1000000] 范围内的整数)。所有数字之间用单个空格隔开。

输出:

每个场景输出以"Scenario #i:"开头,其中 i 是从 1 开始的场景编号。然后输出一行,包含排序该序列所需的最小相邻数字交换次数。每个场景输出后用一个空行结束。