排列是一个由 $n$ 个不同的正整数组成的序列 $p_1, p_2, \dots, p_n$，且每个整数都不超过 $n$。假设序列 $S$ 的 $r(S)$ 表示序列 $S$ 中的逆序对数量（如果 $i < j$ 且 $S_i > S_j$，则称 $(i, j)$ 为 $S$ 的一个逆序对），$l(S)$ 表示序列 $S$ 的长度。给定一个长度为 $n$ 的排列 $P$，你的任务是找到 $P$ 的一个子序列 $S$，使得 $\frac{r(S)}{l(S)}$ 最大。$P$ 的子序列是一个序列 $(p_{i_1}, p_{i_2}, \dots, p_{i_t})$，满足 $0 < i_1 < i_2 < \dots < i_t \le n$。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示排列 $P$ 的长度。第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示排列 $P$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最大的 $\frac{r(S)}{l(S)}$。

如果你的答案与正确答案的绝对误差在 $10^{-6}$ 以内，则被视为正确。

样例

输入格式 1

1
5
3 4 2 5 1

输出格式 1

Case #1: 1.250000000000