一家电子工厂的神秘老板决定做一件非常有趣的事情。她在七个电子设备中隐藏了金晶体管，购买这些设备的人将受邀参加一次神奇而美妙的工厂之旅。
Arnar 和 Solveig 得到消息，当地一家电子商店的某个设备中藏有一个金晶体管。他们首先凑钱买下了所有设备，并将它们排成一排，编号为 0 到 $N-1$。每个设备中都有一定数量的晶体管。随后，他们商定了一个策略来决定谁能得到金晶体管：
首先，Arnar 将选择一个设备区间 $[a, b]$（包含 $a$ 和 $b$），其中 $0 \le a \le b < N$。接下来，Solveig 将选择她想要拿走的一组设备：
- 如果 $a > 0$，她可以选择拿走区间 $[0, a-1]$ 内的所有设备。
- 如果 $b < N-1$，她可以选择拿走区间 $[b+1, N-1]$ 内的所有设备。
- 她总是可以选择拿走区间 $[a, b]$ 内的所有设备。
一旦 Solveig 选择了一组设备，Arnar 就拿走她没有拿走的所有设备。
例如，如果有 3 个设备，Arnar 选择区间 $[1, 1]$，那么 Solveig 可以选择拿走区间 $[0, 0]$、$[1, 1]$ 或 $[2, 2]$。另一方面，如果 Arnar 选择区间 $[1, 2]$，那么 Solveig 可以选择拿走区间 $[0, 0]$ 或 $[1, 2]$。
已知每个设备中晶体管的数量，且 Arnar 和 Solveig 都会尽力最大化自己获得金晶体管的概率（通过获取晶体管数量最多的电子设备来最大化概率），请问 Arnar 获得金晶体管并赢得神奇美妙之旅的概率是多少？
输入格式
输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含五个数字：$N$、$p$、$q$、$r$ 和 $s$。这表示共有 $N$ 个设备，第 $i$ 个设备包含 $((i \times p + q) \pmod r + s)$ 个晶体管。请记住，设备编号从 0 到 $N-1$。
输出格式
对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Arnar 赢得神奇美妙之旅的概率。
如果 $y$ 与正确答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。参见 FAQ 以了解关于误差的解释以及我们接受的实数格式。
数据范围
$1 \le T \le 100$ $1 \le p \le 10^6$ $1 \le q \le 10^6$ $1 \le r \le 10^6$ $1 \le s \le 10^6$
子任务 1
$1 \le N \le 1000$
子任务 2
$1 \le N \le 10^6$
样例
输入格式 1
8 1 1 1 1 1 10 17 1 7 1 2 100 100 200 1 20 17 3 23 100 10 999999 999999 1000000 1000000 2 1 1 1 1 3 1 99 100 1 999999 1000000 999999 1000000 1000000
输出格式 1
Case #1: 0.0000000000 Case #2: 0.6111111111 Case #3: 0.0098039216 Case #4: 0.6471920290 Case #5: 0.6000006000 Case #6: 0.5000000000 Case #7: 0.0291262136 Case #8: 0.6666666667
说明
在第一个样例中，只有一个电子设备，里面有一个晶体管。Arnar 必须选择区间 $[0, 0]$，Solveig 必须选择拿走区间 $[0, 0]$ 内的所有设备。Arnar 不可能赢得神奇美妙之旅。
在第二个样例中，有十个电子设备，晶体管数量分别为 [2, 5, 1, 4, 7, 3, 6, 2, 5, 1]。Arnar 将选择区间 $[4, 5]$，其中包含晶体管数量为 7 和 3 的设备。Solveig 将选择区间 $[6, 9]$，其中包含晶体管数量为 6、2、5 和 1 的设备，留下前六个设备给 Arnar，Arnar 赢得之旅的概率为 22/36。
在第三个样例中，设备分别有 101 和 1 个晶体管。
在第四个样例中，设备晶体管数量为 [103, 120, 114, 108, 102, 119, 113, 107, 101, 118, 112, 106, 100, 117, 111, 105, 122, 116, 110, 104]。
在第五个样例中，设备晶体管数量为 [1999999, 1999998, 1999997, 1999996, 1999995, 1999994, 1999993, 1999992, 1999991, 1999990]。
在第六个样例中，两个设备各有 1 个晶体管。
在第七个样例中，设备晶体管数量为 [100, 1, 2]。
注意，最后一个样例不满足子任务 1 的限制。对于子任务 1，你可能有一个正确的解决方案，但在最后一个样例上返回了错误答案或运行时间过长。