这是问题的简单版本。在这个版本中,$$$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$$$, $$$\bf{n=m}$$$):$$$n$$$、$$$m$$$ 给出了 Lelle 和 Flamm 获胜次数的上限,$$$l$$$ 和 $$$f$$$ 决定了表演的最终分数。
不寻常的附加约束:保证对于每个测试,不存在具有相同对 $$$n$$$、$$$m$$$ 的测试用例对。
输出
对于每个测试用例,输出一个整数 - 成功表演的最高总分。
示例
输入 #1
8 3 3 2 5 4 4 1 4 6 6 2 2 7 7 2 3 9 9 9 1 2 2 1 4 5 5 1 4 8 8 6 7
输出 #1
19 17 18 33 86 9 24 86
输入 #2
1 20000000 20000000 1341 331
输出 #2
33439999007
输入 #3
2 1984 1984 19 84 9982 9982 44 35
输出 #3
204143 788403
注意
在第一个测试用例中,可能的性能如下:
- Flamm 获胜,$$$\gcd(0,1)=1$$$。
- Lelle 获胜,$$$\gcd(1,1)=1$$$。
- Flamm 获胜,$$$\gcd(1,2)=1$$$。
- Flamm 获胜,$$$\gcd(1,3)=1$$$。
- Lelle 获胜,$$$\gcd(2,3)=1$$$。
- Lelle 和 Flamm 同意停止比赛。
最终得分为$$$2\cdot2+3\cdot5=19$$$。
在第三个测试用例中,可能的表现如下:
- Flamm 获胜,$$$\gcd(0,1)=1$$$。
- Lelle 获胜,$$$\gcd(1,1)=1$$$。
- Lelle 获胜,$$$\gcd(2,1)=1$$$。
- Lelle 获胜,$$$\gcd(3,1)=1$$$。
- Lelle 获胜,$$$\gcd(4,1)=1$$$。
- Lelle 获胜,$$$\gcd(5,1)=1$$$。
- Flamm 获胜,$$$\gcd(5,2)=1$$$。
- Flamm 获胜,$$$\gcd(5,3)=1$$$。
- Flamm 获胜,$$$\gcd(5,4)=1$$$。
- Lelle 和 Flamm 同意停止比赛。
最终得分为$$$5\cdot2+4\cdot2=18$$$。请注意,即使 Lelle 和 Flamm 都没有赢得 $$$n$$$ 胜利,他们也可以停止比赛。