CF2002F2.Court Blue (Hard Version)

这是该问题的困难版本。在本版本中，不保证 $n=m$，且时间限制更高。只有在两个版本的问题都被解决后，你才能进行 hack。

在蓝王的宫廷中，Lelle 和 Flamm 正在进行一场表演赛。比赛包含若干轮。在每一轮中，Lelle 或 Flamm 会赢得胜利。

设 $W_L$ 和 $W_F$ 分别表示 Lelle 和 Flamm 的获胜次数。蓝王认为一场比赛是成功的，当且仅当：

• 每一轮结束后，$\gcd(W_L, W_F) \leq 1$；
• 比赛结束时，$W_L \leq n, W_F \leq m$。

注意，对于任意非负整数 $x$，有 $\gcd(0, x) = \gcd(x, 0) = x$。

Lelle 和 Flamm 可以随时决定停止比赛，表演的最终得分为 $l \cdot W_L + f \cdot W_F$。

请帮助 Lelle 和 Flamm 协调他们的胜负，使得表演是成功的，并且总得分最大。

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$）——表示测试用例的数量。

每个测试用例包含一行，包含四个整数 $n$、$m$、$l$、$f$（$2 \leq n \leq m \leq 2 \cdot 10^7$，$1 \leq l, f \leq 10^9$）：$n$ 和 $m$ 分别给出 Lelle 和 Flamm 获胜次数的上限，$l$ 和 $f$ 决定了表演的最终得分。

特殊额外限制：保证每个测试用例中，$n$ 和 $m$ 的组合都是唯一的。

对于每个测试用例，输出一个整数——成功表演的最大总得分。

在第一个测试用例中，一种可能的表演如下：

• Flamm 获胜，$\gcd(0, 1) = 1$。
• Lelle 获胜，$\gcd(1, 1) = 1$。
• Flamm 获胜，$\gcd(1, 2) = 1$。
• Flamm 获胜，$\gcd(1, 3) = 1$。
• Flamm 获胜，$\gcd(1, 4) = 1$。
• Lelle 和 Flamm 同意停止比赛。

最终得分为 $1 \cdot 2 + 4 \cdot 5 = 22$。

由 ChatGPT 4.1 翻译