This is the hard version of the problem. In this version, it is not guaranteed that $$$n=m$$$, and the time limit is higher. You can make hacks only if both versions of the problem are solved.

In the court of the Blue King, Lelle and Flamm are having a performance match. The match consists of several rounds. In each round, either Lelle or Flamm wins.

Let $$$W_L$$$ and $$$W_F$$$ denote the number of wins of Lelle and Flamm, respectively. The Blue King considers a match to be successful if and only if:

after every round, $$$\gcd(W_L,W_F)\le 1$$$;
at the end of the match, $$$W_L\le n, W_F\le m$$$.

Note that $$$\gcd(0,x)=\gcd(x,0)=x$$$ for every non-negative integer $$$x$$$.

Lelle and Flamm can decide to stop the match whenever they want, and the final score of the performance is $$$l \cdot W_L + f \cdot W_F$$$.

Please help Lelle and Flamm coordinate their wins and losses such that the performance is successful, and the total score of the performance is maximized.

Input

The first line contains an integer $$$t$$$ ($$$1\leq t \leq 10^3$$$) — the number of test cases.

The only line of each test case contains four integers $$$n$$$, $$$m$$$, $$$l$$$, $$$f$$$ ($$$2\leq n\leq m \leq 2\cdot 10^7$$$, $$$1\leq l,f \leq 10^9$$$): $$$n$$$, $$$m$$$ give the upper bound on the number of Lelle and Flamm's wins, $$$l$$$ and $$$f$$$ determine the final score of the performance.

Unusual additional constraint: it is guaranteed that, for each test, there are no pairs of test cases with the same pair of $$$n$$$, $$$m$$$.

Output

For each test case, output a single integer — the maximum total score of a successful performance.

Note

In the first test case, a possible performance is as follows:

Flamm wins, $$$\gcd(0,1)=1$$$.
Lelle wins, $$$\gcd(1,1)=1$$$.
Flamm wins, $$$\gcd(1,2)=1$$$.
Flamm wins, $$$\gcd(1,3)=1$$$.
Flamm wins, $$$\gcd(1,4)=1$$$.
Lelle and Flamm agree to stop the match.

The final score is $$$1\cdot2+4\cdot5=22$$$.

Court Blue (Hard Version)

Examples