最近，各种免费游玩的集换式卡牌游戏变得非常流行。这些卡牌游戏通常包含 $n$ 张玩家想要收集的卡牌。玩家首先会获得一个包含 $s$ 张卡牌的初始卡包，保证其中没有重复的卡牌（它们都是唯一的）。之后，玩家可以通过以下两种方式获取新卡牌：

1. 用任意 $d$ 张卡牌换取一张玩家自选的卡牌。这个过程非常快，在本题中，我们假设其耗时为零。
2. 游玩一小时游戏，并以 $p_i$ 的概率赢得一个包含 $k$ 张卡牌的卡包，其中 $i$ 是玩家当前拥有的不同卡牌数量。卡包中的卡牌是从总共 $n$ 张卡牌的集合中独立且均匀随机抽取的（因此可能包含也可能不包含重复卡牌）。

当然，拥有更多的卡牌意味着玩家赢得卡包的概率更高，从而能更快地获得随机卡牌。

吝啬的 Larry 一直在玩这类卡牌游戏。Larry 刚刚拿到了一份这样的游戏（正准备打开他的 $s$ 张卡牌的初始卡包），并希望集齐整套卡牌。假设 Larry 对他的收集过程进行了最优管理，他完成收集所需的最短期望时间是多少？

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例的第一行包含四个整数 $n$ ($1 \le n \le 100$)，表示卡牌总数；$s$ ($0 \le s \le n$)，表示初始拥有的卡牌数量；$k$ ($1 \le k \le 10$)，表示一个卡包中的卡牌数量；以及 $d$ ($1 \le d \le 100$)，表示换取一张新卡牌所需的卡牌数量。测试用例的下一行包含 $n + 1$ 个以空格分隔的实数 $p_0, p_1, \dots, p_n$ ($0.01 \le p_i \le 1$)，表示 Larry 在游玩一小时后赢得卡包的概率。你可以假设 $p_i$ 是非递减的。

输出格式

对于每个测试用例，输出 Larry 完成收集所需的最短期望时间（以小时为单位）。如果答案的绝对误差或相对误差不超过 $10^{-7}$，则视为正确。

样例

样例输入 1

2
1 0 1 1
0.25 1.0
10 2 5 5
0.01 0.1 0.2 0.3 0.4 0.5 0.5 0.5 0.5 0.5 1.0

样例输出 1

4.000000000
10.185962459

说明

在第一个测试用例中，Larry 平均需要游玩四个小时才能赢得他完成收集所需的唯一一张卡牌。