Lucy 是游戏厅的常客。游戏厅里的所有机器都会送出奖券以兑换奖品！Lucy 最喜欢的机器工作原理如下。

该机器只有两个按钮：“Roll”（摇号）和 “Withdraw”（提现）。每当 Lucy 按下 “Roll” 时，机器会在屏幕上的计数器上增加一个在 $0$ 到 $d$ 之间随机生成的实数。在任何时候，她都可以按下 “Withdraw” 来获得与计数器数值相等的奖券，随后计数器清零。如果计数器的数值不是整数，机器会慷慨地将计数器向上取整，然后再发放奖券。

更正式地，机器存储一个实数 $S$，初始时等于 $0$。每次按下 “Roll” 时，机器会生成 $\Delta$ —— 一个在区间 $(0, d)$ 内均匀随机选择的实数。然后，$S$ 增加 $\Delta$ 的值。当按下 “Withdraw” 按钮时，机器将 $S$ 向上取整，给予玩家 $\lceil S \rceil$ 张奖券，然后将 $S$ 重置为零。Lucy 可以在任何时候在屏幕上以任意精度查看 $S$ 的值，并可以用它来决定是继续 “Roll” 还是 “Withdraw”。

Lucy 有足够的游戏币来按下 “Roll” $n$ 次，以及按下 “Withdraw” $k$ 次。找到一种策略，使得 Lucy 能够获得的奖券期望数量最大，并输出这个最大期望数量。

输入格式

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

每个测试用例的唯一一行包含三个整数 $n$、$k$ 和 $d$，分别表示摇号次数、提现次数以及每次摇号数值的上限（$1 \le k \le n \le 2000$；$1 \le d \le 2000$）。

输出格式

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

样例

输入 1

3
3 2 1
5 5 3
7 1 10

输出 1

2.6250000000
10.0000000000
35.5000000000

说明

在第一个测试用例中，$n = 3$ 次摇号，$k = 2$ 次提现，且 $d = 1$，最优策略如下：

Lucy 首先进行一次摇号。根据得到的数值 $S$，有两种可能：

• 数值小于 $\frac{1}{2}$。在这种情况下，Lucy 应该选择提现，然后再摇号两次，最后在结束时提现。在这种情况下，期望的奖券数量为 $1 + \frac{3}{2} = 2.5$（第一次提现获得 $1$ 张奖券，两次摇号后平均获得 $\frac{3}{2}$ 张奖券）。
• 数值至少为 $\frac{1}{2}$。在这种情况下，最优策略是再次摇号、提现，然后进行最后一次摇号，并在结束时提现。对于第一次提现，她有 $\frac{1}{4}$ 的概率只获得一张奖券（在已知第一次摇号结果大于 $\frac{1}{2}$ 的情况下，前两次摇号之和不超过 $1$ 的概率），有 $\frac{3}{4}$ 的概率获得两张奖券。期望的奖券数量为 $1 + 2 \cdot \frac{3}{4} + 1 \cdot \frac{1}{4} = 2.75$。

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

在第二个测试用例中，Lucy 可以在每次摇号后都进行提现，每次平均获得 $2$ 张奖券。

在第三个测试用例中，Lucy 只能提现一次，她应该在全部 $7$ 次摇号后进行提现。