T512574 魔塔

魔塔，顾名思义就是魔物生活的高塔。 你打开了这道题，这表明你是个勇士，但是现在游戏结束了，你将在这里亲手找出击败魔物的最小损耗。

塔中有 $t$ 只魔物，每只魔物有攻击（ $a$ ），防御（ $d$ ），生命（ $h$ ）三种属性。 你将分别与每只魔物进行战斗，你需要求出每场战斗造成的最小最终损耗。 战斗规则如下： 在与每只魔物战斗前，你具有 $c$ 点属性。你可以自由设置自己的攻击 （ $x$ ） 和防御 （ $y$ ），前提是 $x$ 和 $y$ 之和等于 $c$ ，且 $x$，$y$ 都为非负整数。 你将和魔物进行回合制战斗，每回合中，你先手，使 $h$ 减少（$x-d$），魔物后手，造成（$a-y$）点损耗，当 $y>=a$，则损耗为 $0$。如果本回合 $h

第一行一个正整数 $t$，表示数据组数。 接下来 $t$ 行，每行四个非负整数 $h，a，d，c$，意义同上文描述。

$t$ 行，每行一个非负整数，表示最小损耗或无解。

子任务1（ $30$ 分）：所有输入在 $10^7$ 之内。 子任务2（ $70$ 分）：所有输入在 $10^{15}$ 之内。 对于所有数据，保证 $\sum h\le 10^{15}$，$t \le 10$。