There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.
给你一个数字L,代表数字串长。这个数字串每个元素为1或-1.
那么就有这个数列有2^L种可能。
现对每个可能的数字串，求其连续子串和，并将和取绝对值，记下最大的那个值。
再求出所有这些值的总和。
输入总和/2^L
For each test case, output the expectation you are required to calculate. Answers are rounded to 6 numbers after the decimal point.(as shown in the sample output)
3
1
5
10
Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969
当输入2时，有
1 1
1 -1
-1 1
-1 -1
这四种可能，其对应的值分别为(2+1+1+2)=6
6/4=1.5