F2. 宫廷蓝（困难版本）
每个测试点时间限制：$4$ 秒
内存限制：$512$ MB

这是问题的困难版本。在此版本中，不保证 $n=m$，并且时间限制更高。只有同时解决了两个版本的问题，才能进行 Hack。

在蓝王的宫廷中，Lelle 和 Flamm 正在进行一场表演赛。比赛由若干轮组成，每轮要么 Lelle 获胜，要么 Flamm 获胜。

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

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

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

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

请帮助 Lelle 和 Flamm 协调他们的胜负序列，使得比赛成功，并且最终得分最大。

---

输入格式

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

每个测试用例的一行包含四个整数 $n, m, l, f$：

• $2 \le n \le m \le 2 \cdot 10^7$，
• $1 \le l, f \le 10^9$。

附加约束：保证对于每个测试用例，不会出现两个不同的测试用例具有相同的 $(n, m)$ 对。

---

输出格式

对于每个测试用例，输出一个整数——成功比赛中的最大可能总得分。

---

示例

输入 $1$

8
3 4 2 5
4 4 1 4
6 6 2 2
7 9 2 3
8 9 9 1
2 7 1 4
5 9 1 4
5 6 6 7

输出 $1$

22
17
18
37
77
30
41
59

输入 $2$

2
3082823 20000000 1341 331
20000000 20000000 3 5

输出 $2$

10754065643
159999991

输入 $3$

1
139 1293 193 412

输出 $3$

559543

---

说明

第一个测试用例的一个可能比赛过程：

1. Flamm 获胜，$\gcd(0, 1) = 1$；
2. Lelle 获胜，$\gcd(1, 1) = 1$；
3. Flamm 获胜，$\gcd(1, 2) = 1$；
4. Flamm 获胜，$\gcd(1, 3) = 1$；
5. Flamm 获胜，$\gcd(1, 4) = 1$；

然后停止比赛。
最终得分：$1 \cdot 2 + 4 \cdot 5 = 22$。