Goro 有 4 只手臂。Goro 非常强壮。你最好别惹 Goro。Goro 需要对一个包含 $N$ 个不同整数的数组进行排序。算法不是 Goro 的强项；强壮才是 Goro 的强项。Goro 的计划是利用他两只手的手指按住数组中的若干元素，然后用他的第三和第四只拳头尽可能用力地敲击桌面。这将使数组中未被固定的元素飞到空中，随机洗牌，然后落回数组的空位中。

Goro 希望尽快对数组进行排序。如果 Goro 在每次敲击桌面前都能明智地选择要按住哪些元素，那么平均需要敲击多少次才能将给定的数组排好序？Goro 用来按住数组的那两只手拥有无限多的手指。

更准确地说，在每次敲击前，Goro 可以选择数组中任意一个子集来固定在原位。他可以根据之前敲击的结果做出不同的选择。每次敲击都会将未固定的元素进行均匀随机的排列。每种排列出现的概率相等。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行给出数字 $N$。第二行按初始顺序列出数组的 $N$ 个元素。

输出格式

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 是用例编号（从 1 开始），$y$ 是在采取最优固定策略下，敲击桌面的期望次数。绝对误差或相对误差不超过 $10^{-6}$ 的答案将被视为正确。

数据范围

$1 \le T \le 100$；

每个测试用例的第二行包含 $N$ 个最小正整数的一个排列。

内存限制：1GB。

小型数据集（测试集 1 - 可见；10 分）

$1 \le N \le 10$；

时间限制：2 秒。

大型数据集（测试集 2 - 隐藏；20 分）

$1 \le N \le 1000$；

时间限制：4 秒。

样例

样例输入 1

3
2
2 1
3
1 3 2
4
2 1 4 3

样例输出 1

Case #1: 2.000000
Case #2: 2.000000
Case #3: 4.000000

说明

在测试用例 #3 中，一种可能的策略是先按住最左边的两个元素。元素 3 和 4 将可以自由移动。敲击桌面后，它们以正确顺序 $[3, 4]$ 落下的概率为 $1/2$，以错误顺序 $[4, 3]$ 落下的概率为 $1/2$。因此，平均需要 2 次敲击才能使它们按正确顺序排列。之后，Goro 可以按住元素 3 和 4，并敲击桌面直到 1 和 2 以正确顺序落下，这平均需要另外 2 次敲击。总计为 $2 + 2 = 4$ 次敲击。