给定一个由 $N$ 个不同整数组成的序列 $A = [A_1, A_2, \dots, A_N]$，你希望将其重新排列成一个“先升后降”序列（即存在某个下标 $m$（$1 \le m \le N$），使得 $A_1 < A_2 < \dots < A_m > A_{m+1} > \dots > A_N$）。

你可以通过交换序列中相邻的两个元素来重新排列。请计算将序列 $A$ 变为“先升后降”序列所需的最少交换次数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。下一行包含 $N$ 个不同的整数：$A_1, \dots, A_N$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将 $A$ 重新排列为“先升后降”序列所需的最少交换次数。

数据范围

$1 \le T \le 100$。 $1 \le A_i \le 10^9$。 $A_i$ 两两不同。

小数据范围

$1 \le N \le 10$。

大数据范围

$1 \le N \le 1000$。

样例

样例输入 1

2
3
1 2 3
5
1 8 10 3 7

样例输出 1

Case #1: 0
Case #2: 1

说明

在第一个样例中，序列已经符合要求（$m=N=3$），因此不需要交换。

在第二个样例中，交换 3 和 7 可以得到一个“先升后降”序列（此时 $m=3$）。