Description

Lucy 是游戏厅的常客。游戏厅的所有机器都会发放可用于兑换奖品的奖券！Lucy 最喜欢的机器运作方式如下。

这台机器只有两个按钮："投掷"和"取票"。每当 Lucy 按下"投掷"，机器就会将屏幕上的计数器增加一个在 $0$ 到 $d$ 之间随机生成的 实数。在任何时刻，她可以按下"取票"来获得与计数器数值相等的奖券数量，然后计数器会被重置。如果计数器不是整数，机器会慷慨地将计数器向上取整后再发放奖券。

更正式地说，机器存储一个实数 $S$，初始值为 $0$。每次按下"投掷"，机器生成 $\Delta$——一个从区间 $(0, d)$ 中均匀随机选取的 实数。然后，$S$ 增加 $\Delta$ 的值。当按下"取票"按钮时，机器将 $S$ 向上取整，给予玩家 $\lceil S \rceil$ 张奖券，然后将 $S$ 重置为零。Lucy 可以随时在屏幕上看到 $S$ 的值，精度任意，她可以利用这个值来决定是继续投掷还是取票。

Lucy 有足够的游戏币来按下 $n$ 次"投掷"和 $k$ 次"取票"。请找出一个策略，使 Lucy 能获得的期望奖券数最大化，并输出这个最大期望值。

Input Format

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2000$）。接下来是测试用例的描述。

每个测试用例的唯一一行包含三个整数 $n$、$k$ 和 $d$，分别表示投掷次数、取票次数和投掷值的上限（$1 \le k \le n \le 2000$；$1 \le d \le 2000$）。

Output Format

对于每个测试用例，输出 Lucy 能获得的最大期望奖券数，作为一个浮点数。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。

3
3 2 1
5 5 3
7 1 10

2.6250000000
10.0000000000
35.5000000000

Hint

在第一个测试用例中，$n = 3$ 次投掷，$k = 2$ 次取票，$d = 1$，最优策略如下：

Lucy 从一次投掷开始。根据数值 $S$，有两种可能：

• 该数值小于 $\frac 12$。在这种情况下，Lucy 应该取票，然后再投掷两次，最后再次取票。这种情况下的期望奖券数为 $1 + \frac 32 = 2.5$（第一次取票得 $1$ 张奖券，两次投掷后平均获得 $\frac 32$ 张奖券）。
• 该数值至少为 $\frac 12$。在这种情况下，最优策略是再投掷一次，然后取票，接着进行最后一次投掷，最后取票。对于第一次取票，她以 $\frac 14$ 的概率获得 $1$ 张奖券（在第一次投掷超过 $\frac 12$ 的条件下，前两次投掷之和不超过 $1$ 的概率），以 $\frac 34$ 的概率获得 $2$ 张奖券。期望奖券数为 $1 + 2 \cdot \frac 34 + 1 \cdot \frac 14 = 2.75$。

每种情况发生的概率均为 $\frac 12$，因此该策略的总期望值为 $\frac 12 (2.5 + 2.75) = 2.625$。

在第二个测试用例中，Lucy 可以在每次投掷后立即取票，每次平均获得 $2$ 张奖券。

在第三个测试用例中，Lucy 只能取票一次，她应该在所有 $7$ 次投掷后进行取票。

翻译由 DeepSeek V3 完成