F1. 宫廷蓝（简单版）
每次测试时间限制：$3$ 秒
内存限制：$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$。

附加约束：保证对于每个测试用例，不会出现两个不同的测试用例具有相同的 $(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

---

说明

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

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. Lelle 获胜，$\gcd(2, 3) = 1$；

然后停止比赛。
最终得分：$2 \cdot 2 + 3 \cdot 5 = 19$。

---

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

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

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

注意：即使 Lelle 和 Flamm 都没有达到 $n$ 次胜利，也可以停止比赛。