Khodislav 正在玩 D&D（龙与地下城）。此时，他的角色正在与一只怪物战斗，而 Khodislav 因为某些原因对自己的攻击非常有信心，想要用最后一击致命一击消灭敌人。他的角色拥有不同的武器；这些武器能够造成的伤害由掷骰子决定，并由三个数字 $n$、$f$ 和 $m$ 刻画，其中 $n$ 是骰子的数量，$f$ 是每个骰子的面数，$m$ 是修正值。例如，如果 $n = 3$，$f = 8$，$m = 5$，那么你需要掷三个八面骰子，将结果求和，再加上 $5$ 来确定伤害；这通常记作 $3d8 + 5$。

为了消灭怪物，武器必须造成不小于 $D$ 的伤害。请帮助 Khodislav 为他的角色选择一把武器，使他能够以最大的概率杀死怪物。

每次掷骰子都是独立的；掷出骰子每个面的概率是均等的。骰子的各个面上写有从 $1$ 到 $f$ 的所有整数。

输入格式

输入的第一行包含一个整数 $T$ —— 测试用例的数量（$1 \le T \le 5000$）。接下来是 $T$ 个测试用例的描述。

每个测试用例的第一行包含两个整数：$W$ —— 角色的武器数量，以及 $D$ —— 杀死怪物所需的最小伤害（$1 \le W \le 5000$，$1 \le D \le 250$）。

接下来的 $W$ 行描述这些武器。每行包含三个整数：$n$ —— 骰子的数量，$f$ —— 每个骰子的面数，以及 $m$ —— 修正值（$1 \le n \le 10$，$2 \le f \le 20$，$-10 \le m \le 10$）。

保证所有测试用例中武器的总数不超过 $5000$。

输出格式

对于每个测试用例，在单独的一行中输出一个实数 —— 单次攻击造成不小于 $D$ 的伤害的最大概率。答案的绝对误差不能超过 $10^{-11}$。

样例

输入样例 1

2
2 2
1 20 -3
2 2 0
1 11
1 20 -10

输出样例 1

1
0

输入样例 2

3
1 6
1 6 0
1 7
2 6 0
1 100
10 20 10

输出样例 2

0.166666666666667
0.583333333333333
0.799600378342187