Random Sequence

有一个随机序列 $L$，它的每个元素都以相同的概率取 $-1$ 或 $1$。定义 MAVS（Maximum Absolute Value Subsequence）为 $L$ 的所有连续子序列中，元素之和的绝对值最大的那一个（若有多个则任取其一）。给定 $L$ 的长度，请求出 MAVS 的绝对值的期望。

换一种说法：给定长度 $L$，长度为 $L$ 且每个元素为 $1$ 或 $-1$ 的序列共有 $2^L$ 种。对每一种序列，求出它所有连续子串的和，取绝对值后记下其中最大的那个值；把所有序列的这个值加起来，再除以 $2^L$，就是要求的答案。

输入格式

只有一个输入文件。第一行是测试数据组数 $T$，接下来 $T$ 行，每行一个不超过 $1500$ 的正整数，表示序列的长度 $L$。

输出格式

对于每组数据，输出你所求的期望，四舍五入保留小数点后 $6$ 位（格式见样例输出）。

样例输入

3
1
5
10

样例输出

Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969

样例解释

以 $L=2$ 为例（不在本样例中）：长度为 $2$ 的序列共有四种

$$(1,1),\quad (1,-1),\quad (-1,1),\quad (-1,-1),$$

它们对应的值分别为 $2, 1, 1, 2$，总和为 $2+1+1+2=6$，于是期望为 $6/4=1.5$。

数据范围

• 每组数据中 $L\le 1500$。

来源与许可

本题为「Random Sequence」，题面与测试数据整理自 BZOJ 2489。

样例 1

输入

3
1
5
10

输出

Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969