Sunbathing X57809

One of the most important activities on the beach is sunbathing, trying to get that perfect tan. If Roger does not put on any suncream his skin will burn, but if he puts on too much the suncream will block the rays of the sun. Help Roger optimize the use of his suncream.

At each minute, Roger has the option of putting on more suncream, causing his current sun protection factor (SPF) to equal that of the suncream. If he does not put on any suncream, his SPF decreases by one compared to the previous minute, until it reaches $0$. Roger has an ideal sun protection factor $I$, and the benefit to his skin of one minute of sunbathing is given by the following function, where $s$ is Roger’s current SPF:

$$f(s)=1000-(s-I)^2.$$

Input

An integer $1\leq N\leq 1000$ denoting the number of test cases. Each test case consists of four integers $M, S, I, Q$, where $1\leq M\leq 1000$ is the number of minutes that Roger will sunbathe, $1\leq S\leq 50$ is the sun protection factor of the suncream, $0\leq I\leq S$ is Roger’s ideal SPF, and $0\leq Q\leq 20$ is the suncream quantity (the number of times that Roger can put on more suncream).

Output

For each test case, a single line with an integer number representing the maximum total benefit that Roger can achieve to his skin.

Observation

In the first example, the maximum benefit is achieved by applying suncream at the first and third minute. In the second example, Roger’s ideal SPF is $0$, so he should never put on suncream. In the third example, Roger has no suncream available, so he cannot apply any. In the fourth example, the maximum benefit is achieved by applying suncream at the first minute.