题目背景

And it's a long way forward
So trust in me
I'll give them shelter like you've done for me
And I know, I'm not alone
You'll be watching over us
Until ...

一个小女孩斜躺在一个驾驶舱的椅子上，长发从肩膀上飘落到地上。
她的嘴角绽放出微笑，身旁的显示屏写着 “返回 第三行星”。
她怀里的泰迪熊身上写着她的名字，Rin。

—— Shelter

题目描述

Rin 和爸爸还在地球上时，他们经常玩一个石子游戏。

爸爸摆出了 $n$ 堆石子，这 $n$ 堆石子编号为 $1$ 到 $n$。

游戏规则是这样的，每次 Rin 可以抓取石子，有两种抓取方式：

• 选择一个数 $i$，把第 $i$ 堆石子抓取走，代价为 $i \times p$。
• 选择两个数 $i,j$，把第 $i$ 堆和第 $j$ 堆石子抓走，代价为 $|i-j| \times q$。

其中 $p,q$ 为爸爸提前定好的常数。

Rin 想知道，抓取完所有石子至少需要多少代价。

还剩 1919810114514 秒第三行星的灾难就要降临了，爸爸还需要 1919810114513.7 秒的时间把 Rin 安放到驾驶舱里，并启动机器让 Rin 进入 “Shelter” 里，因此，你只有 0.3 秒的时间帮助 Rin 算出这个结果哦！

输入格式

本题多测，第一行一个整数 $T$ 代表数据组数。
接下来 $t$ 行，每行三个整数 $n,p,q$ 代表石子堆数，和两个常数。

输出格式

$T$ 行每行一个整数代表答案。

2
5 2 3
4 1 5

8
8

提示

样例 1 解释

第一组数据：

1. 利用第一个操作，拿走第 $1$ 堆石子，代价为 $1 \times 2=2$。
2. 利用第二个操作，拿走第 $2,3$ 堆石子，代价为 $|2-3| \times 3=3$。
3. 利用第二个操作，拿走第 $4,5$ 堆石子，代价为 $|4-5| \times 3=3$。

最小代价为 $2+3+3=8$。

第二组数据：

1. 利用第一个操作，拿走第 $1$ 堆石子，代价为 $1 \times 1=1$。
2. 利用第一个操作，拿走第 $2$ 堆石子，代价为 $2 \times 1=2$。
3. 利用第二个操作，拿走第 $3,4$ 堆石子，代价为 $|3-4| \times 5=5$。

最小代价为 $1+2+5=8$。

数据规模与约定

本题采用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^9$，$0 \le p,q \le 100$，$1 \le T \le 10^6$。

附件中的 Extra Example 满足 $T=10^4$，可供调试使用。

Source：JROI-2 Summer Fun Round - T1

Idea&Sol：一只书虫仔

Std&Data：Tony2

Retest：Cocoly1990