This problem is a programming version of Problem 141 from projecteuler.net
A positive integer, , is divided by and the quotient and remainder are and respectively. In addition , , and are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.
For example, divided by has quotient and remainder . It can also be seen that , , are consecutive terms in a geometric sequence (common ratio ). We will call such numbers, $n, progressive.
Some progressive numbers, such as and , happen to also be perfect squares. The sum of all progressive perfect squares below one hundred thousand is .
Some progressive numbers, such as and , are very close to becoming perfect squares; in fact, their distance from the nearest perfect square is one.
Given and , find the sum of all progressive numbers below that are at most away from a perfect square.
Input Format
The first line of input contains , the number of test cases.
Each test case consists of a single line containing two integers separated by a single space: and .
Constraints
For test cases worth 50% of the total points:
For test cases worth 100% of the total points:
Output Format
For each test case, output one line containing a single integer: the answer for that test case.
Sample Input
2
0 100000
1 100000
Sample Output
124657
288467
Explanation
The first test case corresponds to the example given in the problem statement, so the answer is .