If you want to find the most innovative students at RHHS, there’s only one place to look: TEJ4M1. Here, the students are always finding new ways to challenge reality and solve unknown problems. On an average day in TEJ4M1, the students had an extra-special idea. They decided to stack all of the AA batteries in the classroom into triangles of different base sizes, as shown below.
However, they encountered a little problem. Out of the batteries available in the classroom, the rest of the class (the unproductive part) needed batteries in order to use their power-hungry drone remotes. Due to this ridiculous restriction, the highly motivated students decided they only had one option: to maximize the awesomeness they could get with the limited supply to batteries they had. This involved creating battery triangles of ascending base length, following the set of natural numbers , and using as many of the available batteries as possible.
In order to help them, you, as the Gordon of the class, need to find the number of batteries required to create the maximum number of pyramids.
The first line will contain , the number of test cases.
The next lines will contain two space separated integers, and .
For test cases worth 20 of 100 points, .
For test cases worth an additional 30 points, .
Output a single integer, representing the number of batteries required to create the maximum number of pyramids with the given number of available batteries.
Sample Input 1
1 40 10
Sample Output 1
Explanation for Sample 1
Of the 40 available batteries, the rest of the class needs 10. That leaves 40 - 10 = 30 batteries for the triangles. The first four available triangles result in triangles with 1, 3, 6, and 10 batteries. 1 + 3 + 6 + 10 = 20. Adding the next sized triangle, which contains 15 batteries, will bring the total battery requirement up to 20 + 15 = 35, which is more than the available 30. Thus, 20 batteries is the maximum the students could use.
Sample Input 2
1 10000 1000
Sample Output 2
Explanation for Sample 2
Use the first 36 triangles. 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55 + 66 + 78 + 91 + 105 + 120 + 136 + 153 + 171 + 190 + 210 + 231 + 253 + 276 + 300 + 325 + 351 + 378 + 406 + 435 + 465 + 496 + 528 + 561 + 595 + 630 + 666 = 8436