As a celery sticks manufacturer, you have a celery stick of length $n$.
There is a standard length for the celery sticks, denoted as $l$. Deviations from this standard length will result in a lower selling price. Specifically, if the length of a celery stick is $x$, the selling price would be $p - |x - l|$, where $p$ is a given value. Note that the selling price can be negative, as you should pay for garbage disposal.
You can cut the celery sticks in any way you wish, as long as the lengths of the pieces are still integers, to maximize your profit after selling them. Please determine the total maximum profit you can achieve.
The input contains $T$ test cases, the first line is an integer $T$ $(1 \le T \le 10^5)$, denoting the number of test cases.
For each test case, the input contains three integers $n$, $p$, and $l$, $(1 \le n, p, l \le 10^9)$, denotes the length of initial celery stick, the highest selling price of a celery stick, and the standard length of the celery sticks.
For each test case, output the maximum profit you can get.
6 10 5 2 10 1 3 11 5 2 11 1 3 12 8 7 10 1 20\n · · \n · · \n · · \n · · \n · · \n · · \n
40 2 44 3 24 -9\n \n \n \n \n \n
In the 1st test case, cut the celery stick into 10 celery sticks of length 1, each sells \$4, the total profit is \$40.
In the 2rd test case, cut the celery stick into the lengths of {3,3,4}, the selling price would be {\$1,\$1,\$0}, therefore, the total profit is \$2.
In the 6th test case, do nothing to get the selling price \$-9, which is the best solution. Any cut will result in much money loss.