你曾去过小青鱼王国吗？那是一个美丽——甚至可以说是神奇——的国度，可以被想象为一条由 $2 \times 10^{100} + 1$ 个格子组成的直线，格子从 $-10^{100}$ 到 $10^{100}$ 连续编号。

王国的座右铭是“In Code We Trust”（我们信仰代码），这体现了算法竞赛在这个可爱地方的重要性。这里的骄傲与荣耀便是环球杯（Universal Cup）。

图 1：举办第二届环球杯总决赛。

王国的国王——也就是小青鱼本人——即将为定于 2026 年举办的第三届环球杯总决赛选择承办城市。共有 $n$ 支合格的队伍，其中第 $i$ 支队伍目前居住在格子 $x_i$。

在决赛开始前，所有队伍必须前往选定的承办格子。在王国中，有两种可行的交通方式：

• 铁路：王国有一条主铁路线，每个格子 $i$ 都与 $i-1$ 和 $i+1$ 直接相连。在两个相邻格子之间移动需要花费 $1$ 元。
• 航班：每个格子也都有一个机场。从格子 $i$ 出发，可以乘飞机前往 $i - a$ 或 $i + a$，每次飞行的固定花费为 $b$ 元。

小青鱼并不关心旅途需要多长时间，但总交通费用是一个严重的问题，因为预算是有限的。你的任务是确定：如果最优地选择承办格子，小青鱼最少需要准备多少总资金。

输入格式

单个测试文件包含多个测试用例。输入的第一行包含一个整数 $T$ ($T \ge 1$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $n$，$a$ 和 $b$ ($n \ge 1$, $1 \le a, b \le 10^{12}$)，分别表示合格队伍的数量以及航空公司的参数。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($-10^{12} \le x_i \le 10^{12}$)，表示每支队伍的初始位置。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，输出单行，包含一个整数，表示答案。

样例

输入格式 1

3
3 5 1
1 11 22
4 5 3
1 3 5 8
7 6 3
2 9 15 24 33 40 53

输出格式 1

5
7
55

说明

对于第一个测试用例，一种最优方案是将第三届环球杯总决赛放在第 $11$ 个格子举办。