在你的基地里，你通过挖掘沙石建造了一个深坑，坑内设有楼梯和电梯。深坑深入地下，你在不同的楼层存放设备，并在最深处存放奶酪以供陈化，特别是 Eidam 奶酪。你经常会下楼散步，但你常常想知道，是步行回到地面更快，还是部分或全程乘坐电梯更快。

你知道你自己和电梯的位置及速度。地面楼层编号为 0，正数表示地下楼层，数值代表其距离地面的深度。你在火星上是孤独的，所以只有你会使用电梯。此外，（你和电梯）启动和停止移动几乎不需要时间，因此可以忽略不计。当电梯被呼叫到多个楼层时，它会按照呼叫的顺序依次前往。这部电梯并不特殊——一旦你进入电梯，你可以命令它前往任意楼层。在这种情况下，必须先处理之前所有的呼叫。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。接下来 $T$ 行，每行包含一个测试用例。每个测试用例由四个整数组成：$Y_p, L_p, Y_s, L_s$，其中 $0 \le Y_p, L_p \le 10^9$ 分别是你和电梯的初始楼层，$0 < Y_s, L_s \le 10^6$ 分别是你和电梯移动一层所需的时间。

输出格式

对于每个测试用例，输出一个整数，表示你从初始楼层移动到第 0 层所需的最短时间。

样例

输入 1

2
2 20 10 2
10 20 10 2

输出 1

20
40

说明

样例 1 包含两个测试用例。在第一个用例中，你宁愿步行到 0 层，也不愿等待 18 层之外的电梯。在第二个用例中，最快方式的一个例子是：你呼叫电梯，同时步行上楼 1 层，然后你呼叫电梯前往地下第 9 层并等待电梯，随后乘坐电梯到达 0 层。