Getting Your Money Back

For some weird security reason, Cuber Bank now shuts down the interface where you can check your balance on your bank account. From now on, when you click the "check" button on your interface, they will show you a range, saying that the money in your account has to be one of the integers between $x$ and $y$, inclusive. Yes, less informative, but more secure.

Perhaps you are not convinced of their explanation, and you get annoyed as much as I do. Moreover, you are the kind of person who won't get a good sleep until you see from your screen that your beloved money is lying right in your bank account, safe and sound. Since Cuber Bank can't provide this service any more, it's time to withdraw all your money and go for another bank.

However, when you went to the bank the other day, the manager Cuber QQ told you that, there have been so many people trying to close their account recently, so that they have to do something: to make the rule that you have to pay an extra fee each time you attempt to withdraw money from your account.

There is a machine you can interact with. After you insert your card, the proceses goes in an interactive way, just like playing a game. The machine first tells you a range, $[x, y]$, which your balance is currently between. Then at each attempt, you type in the amount of money (also an integer) you want to withdraw; the machine then tell you whether your operation is successful or not (successful if and only if the amount fits your balance). In order to prevent excessive requests that cause great pressure on the system, if successful you have to pay $a$ dollars for this attempt; if fail you have to pay $b$ dollars. You pay these fees with cash, brought by yourself. You can do more attempts until you are very convinced that there is no more money on your account. The machine will not disclose any further information about any range after the first attempt.

Devise a strategy that will cost you the least dollars of extra fees in the worst case, in order to retrieve all the money from your account.

The first line of the input is an integer $t$ ($1 \le t \le 10^4$), which means $t$ test cases will follow.

The follows $t$ test cases, each is one line of space-separated integers $x$, $y$, $a$, $b$ ($0 \le x \le y \le 2 \cdot 10^5$, $0 \le a, b \le 10^9$).

The sum of $y$ in all test cases does not exceed $8 \cdot 10^6$.

For each test case, output the extra dollars you have to prepare in one line.

Here are some notes for the sample below.

In sample 1, the first attempt should be a retrieval of $1$ dollar. If this works, there might be one more dollar (or not), for which you need to pay $2 + \max(2, 3) = 5$ altogether; if it fails, then you are done, for which you need to pay $3$ dollars.

In sample 2, try $2$ dollars first, pay $3$ dollars if succeeded; otherwise, the balance could be $0$ or $1$ dollars, for which you will need to pay $2 + \max(2, 3) = 5$ dollars altogether.

2
0 2 2 3
0 2 3 2

5
5

2019 Multi-University Training Contest 7