这是问题的困难版本。该版本不保证$$$n=m$$$,且时间限制较高。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
蓝王的法庭上,莱尔和弗拉姆正在进行一场表演赛。比赛由几轮组成。在每一轮中,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\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$$$ 的测试用例对。
输出
对于每个测试用例,输出一个整数 - 成功表演的最高总分。
示例
输入 #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
注意
在第一个测试用例中,可能的性能如下:
- 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\cdot2+4\cdot5=22$$$。