Description

When Rin and her father were still on Earth, they often played a stone game.

Dad set up $n$ piles of stones, numbered from $1$ to $n$.

The rules are as follows. Each time, Rin can take stones in one of two ways:

• Choose a number $i$, take away the $i$-th pile of stones, with a cost of $i \times p$.
• Choose two numbers $i,j$, take away the $i$-th and $j$-th piles of stones, with a cost of $|i-j| \times q$.

Here, $p,q$ are constants set in advance by Dad.

Rin wants to know the minimum total cost to take away all the stones.

There are only 1919810114514 seconds left before the disaster strikes the Third Planet. Dad still needs 1919810114513.7 seconds to place Rin into the cockpit and start the machine to let Rin enter "Shelter". Therefore, you only have 0.3 seconds to help Rin compute the result!

Input Format

This problem has multiple test cases. The first line contains an integer $T$ representing the number of test cases.
The next $T$ lines each contain three integers $n,p,q$, representing the number of stone piles and the two constants.

Output Format

Output $T$ lines, each containing one integer representing the answer.

2
5 2 3
4 1 5

8
8

Hint

Explanation for Sample 1

First test case:

1. Use the first operation to take away pile $1$, with cost $1 \times 2=2$.
2. Use the second operation to take away piles $2,3$, with cost $|2-3| \times 3=3$.
3. Use the second operation to take away piles $4,5$, with cost $|4-5| \times 3=3$.

The minimum cost is $2+3+3=8$.

Second test case:

1. Use the first operation to take away pile $1$, with cost $1 \times 1=1$.
2. Use the first operation to take away pile $2$, with cost $2 \times 1=2$.
3. Use the second operation to take away piles $3,4$, with cost $|3-4| \times 5=5$.

The minimum cost is $1+2+5=8$.

Constraints and Notes

This problem uses bundled tests.

• Subtask 1 (1 pts): $p,q =0$.
• Subtask 2 (1 pts): $n=1$.
• Subtask 3 (30 pts): $T \le 5 \times 10^4$, $n \le 5 \times 10^5$.
• Subtask 4 (33 pts): $T \le 10^6$, $n \le 5 \times 10^5$.
• Subtask 5 (35 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le n \le 10^9$, $0 \le p,q \le 100$, $1 \le T \le 10^6$.

The Extra Example in the attachment satisfies $T=10^4$ and can be used for debugging.

Source: JROI-2 Summer Fun Round - T1

Idea & Solution: 一只书虫仔

Standard Solution & Data: Tony2

Retest: Cocoly1990

Translated by ChatGPT 5