Epsilon的史莱姆

题目描述

最近科林迷上了一款策略解谜角色扮演游戏：《超级代数乱斗》。在游戏中，科林化身为一艘拥有魔法数学能力的船！他正踏上追求荣耀的征程，斩杀肆虐动物王国的恐怖怪物。每场战斗都是一个需要用逻辑和简单代数解决的谜题！

就在刚才，科林来到了下一个战场：Epsilon 河口。这里的统治者是史莱姆，不同于杀戮尖塔里的史莱姆，它们有一项恶心的分裂技能(杀戮尖塔的也挺恶心的)——“SPLASH”：一旦史莱姆受伤，假设其剩余生命值为 x，它会立即分裂成两只史莱姆，生命值分别为 ⌊x/2⌋（x除以2的下取整）和 ⌈x/2⌉（x除以2的上取整）；新产生的史莱姆后续受伤时也能继续使用这项技能。生命值为0的史莱姆会立即死亡。

不过，我们的挑战者科林恰好有对付它们的最佳武器：“SHOCK”魔法卷轴！具体来说，科林每次使用该卷轴，都会对所有怪物造成 y 点伤害。如果某只怪物在科林使用卷轴前的生命值不超过 y，那么它会在卷轴使用后立即死亡。

假设 y=5，场上有两只史莱姆，生命值分别为 x₁=25、x₂=8。科林使用一次卷轴后，它们的生命值变为 x₁=20、x₂=3。随后它们立即分裂：第一只史莱姆分裂成两只生命值为10和10的史莱姆；第二只分裂成两只生命值为2和1的史莱姆。

科林的魔法卷轴可以使用任意次数，因此消灭史莱姆只是时间问题。但反复点击鼠标太麻烦了，所以科林希望你计算：给定场上史莱姆的初始状态，他至少需要使用多少次卷轴，才能确保所有怪物都被消灭？

输入格式

第一行包含一个整数 T（1 ≤ T ≤ 10⁵），表示测试用例的数量。 每个测试用例：

• 第一行包含两个整数 n、y（1 ≤ n ≤ 10⁵，1 ≤ y ≤ 10¹⁸），分别表示战场上史莱姆的数量，以及每次使用魔法卷轴对每个史莱姆造成的伤害。
• 第二行包含 n 个整数 x₁, x₂, ..., xₙ（1 ≤ xᵢ ≤ 10¹⁸），表示每个史莱姆的初始生命值。

保证所有测试用例的 n 之和不超过 10⁶。

输出格式

输出 T 行，每行一个整数表示至少需要使用多少次卷轴。

样例 1

1
2 5
25 8

3

提示

{25, 8} -> {10, 10, 2, 1} -> {3, 2, 3, 2} -> ∅