New Bakery
Description
Bob decided to open a bakery. On the opening day, he baked $n$ buns that he can sell. The usual price of a bun is $a$ coins, but to attract customers, Bob organized the following promotion:
- Bob chooses some integer $k$ ($0 \le k \le \min(n, b)$).
- Bob sells the first $k$ buns at a modified price. In this case, the price of the $i$-th ($1 \le i \le k$) sold bun is $(b - i + 1)$ coins.
- The remaining $(n - k)$ buns are sold at $a$ coins each.
Note that $k$ can be equal to $0$. In this case, Bob will sell all the buns at $a$ coins each.
Help Bob determine the maximum profit he can obtain by selling all $n$ buns.
Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The only line of each test case contains three integers $n$, $a$, and $b$ ($1 \le n, a, b \le 10^9$) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.
For each test case, output a single integer — the maximum profit that Bob can obtain.
Input
Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The only line of each test case contains three integers $n$, $a$, and $b$ ($1 \le n, a, b \le 10^9$) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.
Output
For each test case, output a single integer — the maximum profit that Bob can obtain.
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000
17
35
100
45
1000000000000000000
1000000000000000000
500500
Note
In the first test case, it is optimal for Bob to choose $k = 1$. Then he will sell one bun for $5$ coins, and three buns at the usual price for $4$ coins each. Then the profit will be $5 + 4 + 4 + 4 = 17$ coins.
In the second test case, it is optimal for Bob to choose $k = 5$. Then he will sell all the buns at the modified price and obtain a profit of $9 + 8 + 7 + 6 + 5 = 35$ coins.
In the third test case, it is optimal for Bob to choose $k = 0$. Then he will sell all the buns at the usual price and obtain a profit of $10 \cdot 10 = 100$ coins.