Court Blue (Easy Version)
Contest: EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)
Difficulty rating: 2600
Tags: brute force, dfs and similar, dp, math, number theory

This is the easy version of the problem. In this version, $$$n=m$$$ and the time limit is lower. You can make hacks only if both versions of the problem are solved.

In the court of the Blue King, Lelle and Flamm are having a performance match. The match consists of several rounds. In each round, either Lelle or Flamm wins.

Let $$$W_L$$$ and $$$W_F$$$ denote the number of wins of Lelle and Flamm, respectively. The Blue King considers a match to be successful if and only if:

- after every round, $$$\gcd(W_L,W_F)\le 1$$$;
- at the end of the match, $$$W_L\le n, W_F\le m$$$.

Note that $$$\gcd(0,x)=\gcd(x,0)=x$$$ for every non-negative integer $$$x$$$.

Lelle and Flamm can decide to stop the match whenever they want, and the final score of the performance is $$$l \cdot W_L + f \cdot W_F$$$.

Please help Lelle and Flamm coordinate their wins and losses such that the performance is successful, and the total score of the performance is maximized.

Input format:
The first line contains an integer $$$t$$$ ($$$1\leq t \leq 10^3$$$) — the number of test cases.

The only line of each test case contains four integers $$$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$$$ gives the upper bound on the number of Lelle and Flamm's wins, $$$l$$$ and $$$f$$$ determine the final score of the performance.

Unusual additional constraint: it is guaranteed that, for each test, there are no pairs of test cases with the same pair of $$$n$$$, $$$m$$$.

Output format:
For each test case, output a single integer — the maximum total score of a successful performance.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test case, a possible performance is as follows:

- Flamm wins, $$$\gcd(0,1)=1$$$.
- Lelle wins, $$$\gcd(1,1)=1$$$.
- Flamm wins, $$$\gcd(1,2)=1$$$.
- Flamm wins, $$$\gcd(1,3)=1$$$.
- Lelle wins, $$$\gcd(2,3)=1$$$.
- Lelle and Flamm agree to stop the match.

The final score is $$$2\cdot2+3\cdot5=19$$$.

In the third test case, a possible performance is as follows:

- Flamm wins, $$$\gcd(0,1)=1$$$.
- Lelle wins, $$$\gcd(1,1)=1$$$.
- Lelle wins, $$$\gcd(2,1)=1$$$.
- Lelle wins, $$$\gcd(3,1)=1$$$.
- Lelle wins, $$$\gcd(4,1)=1$$$.
- Lelle wins, $$$\gcd(5,1)=1$$$.
- Flamm wins, $$$\gcd(5,2)=1$$$.
- Flamm wins, $$$\gcd(5,3)=1$$$.
- Flamm wins, $$$\gcd(5,4)=1$$$.
- Lelle and Flamm agree to stop the match.

The final score is $$$5\cdot2+4\cdot2=18$$$. Note that Lelle and Flamm can stop the match even if neither of them has $$$n$$$ wins.

Example input:
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

Example output:
19
17
18
33
86
9
24
86

Example input:
1
20000000 20000000 1341 331

Example output:
33439999007

Editorial:
We can view the problem as a walk on a grid; we start from the upper left corner $$$(1,1)$$$, going down or right each step, without passing through any $$$\gcd(x,y)\neq 1$$$.
A general idea is that primes are very useful; we can use this idea to reduce the scope of our consideration.
When $$$n$$$ is large enough$$$(n > 10)$$$, the second largest prime below $$$n$$$ will be greater than $$$\frac{n}{2}$$$; this will be a useful property in the analysis below.
Let $$$p$$$ be the maximum prime below $$$n$$$; then all $$$(x,p)$$$ and $$$(p,x)$$$ are legal cells, except $$$(p,p)$$$. However, these cells might not be reachable from $$$(1,1)$$$.
Let $$$q$$$ be the second maximum prime below $$$n$$$; then all cells on the line $$$(q,n)-(q,p)-(p,p)-(p,q)-(n,q)$$$ are reachable and legal, except $$$(p,p)$$$.
Thus, we only need to consider all cells to the bottom right of this line. Since the probability of any given integer to be prime is $$$O(\frac1\ln)$$$, we can guess that this area is not very large; in fact, when $$$n\le 2\times10^7$$$, the area(of the rectangular region) is about $$$3.5\times 10^4$$$, and the sum of the largest $$$10^3$$$ of them is around $$$2\times10^7$$$. We can run a dp on the cells and pass within the constraints.