鲍勃决定开一家面包店。开业当天,他烤了 $$$n$$$ 的面包可以卖。一个包子的通常价格是$$$a$$$硬币,但为了吸引顾客,鲍勃组织了以下促销活动:
- Bob 选择某个整数 $$$k$$$ ($$$0 \le k \le \min(n, b)$$$)。
- 鲍勃以修改后的价格出售了第一批 $$$k$$$ 面包。在这种情况下,第 $$$i$$$ ($$$1 \le i \le k$$$) 售出的小圆面包的价格为 $$$(b - i + 1)$$$ 硬币。
- 剩余的 $$$(n - k)$$$ 面包每个售价为 $$$a$$$ 硬币。
请注意,$$$k$$$ 可以等于 $$$0$$$。在这种情况下,鲍勃将以每个 $$$a$$$ 硬币的价格出售所有面包。
帮助鲍勃确定出售所有 $$$n$$$ 面包可以获得的最大利润。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n, a, b \le 10^9$$$) — 包子的数量、包子的通常价格以及以修改后的价格出售的第一个包子的价格。
输出
对于每个测试用例,输出一个整数——Bob 可以获得的最大利润。
示例
输入 #1
7 4 4 5 5 5 9 10 10 5 5 5 11 1000000000 1000000000 1000000000 1000000000 1000000000 1 1000 1 1000
输出 #1
17 35 100 45 1000000000000000000 1000000000000000000 500500
注意
在第一个测试用例中,Bob 最好选择 $$$k = 1$$$。然后他会以 $$$5$$$ 硬币的价格出售一个面包,并以正常价格出售三个面包,每个面包为 $$$4$$$ 硬币。那么利润将为$$$5 + 4 + 4 + 4 = 17$$$ 硬币。
在第二个测试用例中,Bob 最好选择 $$$k = 5$$$。然后他会按照修改后的价格出售所有的包子,获得$$$9 + 8 + 7 + 6 + 5 = 35$$$ 币的利润。
在第三个测试用例中,Bob 最好选择 $$$k = 0$$$。然后他会以平常的价格出售所有的包子,获得$$$10\cdot 10 = 100$$$币的利润。