P7777 『JROI-2』Shelter

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](https://www.bilibili.com/video/BV1ys41147Gv) ---

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$ 行每行一个整数代表答案。

#### 样例 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](https://www.luogu.com.cn/contest/30241) - T1 Idea&Sol：[一只书虫仔](/user/114914) Std&Data：[Tony2](/user/171288) Retest：[Cocoly1990](/user/183026)