In your base you have dug through sand and rock to construct a deep pit with stairs and a lift. The pit goes very deep into the ground where on various floors you leave equipment and on the deepest levels you leave cheeses to age, particularly Eidam. You often take a stroll downstairs, but wonder whether it is faster to go up to the surface by foot or take a lift for a part or all of the trip.
You know the position and the speed of yourself and the lift. The surface floor is numbered $0$, positive numbers denote underground floors by their distance to the surface. You are alone on the Mars so only you will use the lift. Also, it takes (you and lift) almost no time to start and stop moving so you will neglect these. When the lift is called to multiple floors, it moves to them in the same order in which it was called. The lift is not very special – once you enter it, you may order it to go to an arbitrary floor. In such case, any previous calls must be processed first.
The first input line contains a single integer $T$ ($1 \le T \le 10^4$), the number of test cases.
Next $T$ lines contain one test case each. Each test case is composed of four integers: $Y_ p$, $L_ p$, $Y_ s$, $L_ s$ where $0 \le Y_ p, L_ p \le 10^9$ are the initial floors of you and the lift, and $0 < Ys, Ls \le 10^6$ are the times it takes you and of the lift to move by one floor, respectively.
For each test case, print a single integer – the minimum time it takes you to move from your initial floor to the $0$’th floor.
The first sample contains two test cases. In the first one, you will rather walk to $0$’th floor than to wait for the lift which is $18$ floors away.
In the second test case, an example of the fastest way is when you call the lift and walk 1 floor upstairs in the meantime, then you call the lift to $9$’th underground floor and wait for the lift which you then take to the $0$’th floor.
|Sample Input 1||Sample Output 1|
2 2 20 10 2 10 20 10 2