410041: GYM103931 C Coffee Overdose

You're doing your giant project, which will due by the day after tomorrow. You still have some time, yet your body and mind are falling asleep and keeping your head knocking on the desktop.

Don't worry! You have a sufficient supply of coffee – everybody knows that coffee contains caffeine, and caffeine will keep you awake. One issue you might notice is that coffee will keep you awake for a period, but after that, you will be more exhausted. To be more productive, you must use your fatigue weapon wisely.

We use the stamina $$$S$$$ to evaluate how energetic you are. At each second, you contribute $$$S$$$ points of completeness to your project, and your stamina will decrease by $$$1$$$ after that. When your stamina decreases to $$$0$$$ or less, you will lose control and fall into dreamland.

You can drink a shot of coffee at the beginning of each second, and the effect will last for $$$C$$$ seconds. During the effect of the coffee, you can not drink another shot and your stamina will be fixed at the beginning. After that, your stamina will reduce $$$C + 1$$$, i.e., $$$1$$$ extra cost caused by coffee.

Your goal is to maximize the productivity before you are too sleepy. Given $$$S$$$ and $$$C$$$, find the optimal schedule to maximize the total points of completeness.

The first line contains one integer $$$T (1 \leq T \leq 10^5)$$$, the number of test cases.

For each case, there is only one line containing two integers, $$$S, C ~(1 \leq S, C \leq 172\,800 = 2\times 24 \times 60 \times 60)$$$, denoting your initial stamina and the coffee period length.

For each test case, output a single integer in a separate line denoting the maximum possible total points of completeness.

4
1 2
2 1
10 4
172800 172800

2
3
63
29859840000

For the first sample case, you may drink the coffee at the very beginning, and the stamina sequence will be $$$1, 1, -2$$$.

For the second sample case, since the coffee is literally not working for you, you should stop overdosing and keep a healthier life.

For the third sample case, one optimal schedule is to drink a shot at the beginning of $$$3$$$-rd and $$$7$$$-th second respectively, and the stamina sequence will be $$$10, 9, 8, 8, 8, 8, 3, 3, 3, 3, -2$$$.