K. Welfare
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer Steve wants to provide welfare for the cows on his farm!

Steve has a lot of grass to distribute to the cows, but he wants to give them the right to choose. So he sets up two options A and B. Cows that choose A will share $$$x$$$ kilograms of grass (that is, if there are $$$k$$$ cows that choose A, and $$$k \gt 0$$$, then each of these $$$k$$$ cows will receive $$$\frac{x}{k}$$$ kilograms of grass, without rounding), while cows that choose B will individually receive $$$y$$$ kilograms of grass.

On Steve's farm, there are $$$n$$$ selfless cows and $$$m$$$ selfish cows. Steve has a good relationship with the cows; he knows which cows are selfless and which are selfish, and each cow knows the values of $$$x$$$ and $$$y$$$. The selection process follows these steps:

  1. If $$$n \gt 0$$$, all selfless cows elect the smartest among them to decide how each selfless cow should choose, so that the total weight of grass received by all cows is maximized. The selfless cow knows how the selfish cows will decide what to choose.
  2. If $$$m \gt 0$$$, all selfish cows make their choices independently and simultaneously. They know the choices of the selfless cows. A selfish cow will assume that all other selfish cows choose B. In this case, if choosing A gives it a weight of grass that is strictly greater than the weight it would receive by choosing B, it will choose A; otherwise, it will choose B.

Steve has already determined the values of $$$x$$$ and $$$y$$$, and he wants to know how many kilograms of grass he will need to distribute in total to the cows. It can be proven that the answer will always be an integer.

Input

This problem has multiple test cases. The first line contains a positive integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), indicating the number of test cases.

Each test case contains four integers $$$n,m,x,y$$$ ($$$0 \leq n,m,x,y \leq 10^9$$$).

Output

For each test case, output a single integer on a new line, representing the answer.

Example
Input
9
0 0 114514 1919810
1 2 3 4
2 3 8 3
0 0 1 0
0 0 0 1
0 2 5 4
0 2 4 5
2 0 5 4
2 0 3 1
Output
0
12
17
0
0
5
10
9
4
Note

In the first test case, since there are no cows, he only needs to distribute $$$0$$$ kilograms of grass.

In the second test case, one possible scenario is: in the first step, the only selfless cow chooses B; in the second step, a selfish cow will assume that all other selfish cows choose B. In this case, if it chooses A, it will receive $$$\frac{3}{0+1}=3$$$ kilograms of grass, and if it chooses B, it will receive $$$4$$$ kilograms of grass. Therefore, both selfish cows choose B. In the end, all cows choose B, receiving a total of $$$4 \times (1+2) = 12$$$ kilograms of grass. It can be proven that no matter how the selfless cow chooses, the total weight of grass received by all cows will not exceed $$$12$$$.

In the third test case, one possible scenario is: in the first step, both selfless cows choose A; in the second step, a selfish cow will assume that all other selfish cows choose B. In this case, if it chooses A, it will receive $$$\frac{8}{2+1}=\frac{8}{3}$$$ kilograms of grass, and if it chooses B, it will receive $$$3$$$ kilograms of grass. Therefore, all three selfish cows choose B. In the end, there are $$$2$$$ cows that choose A and $$$3$$$ cows that choose B, receiving a total of $$$\frac{8}{2} \times 2 + 3 \times 3 = 17$$$ kilograms of grass. It can be proven that no matter how the selfless cows choose, the total weight of grass received by all cows will not exceed $$$17$$$.