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.
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 .
For test cases worth 50% of the total points:
For test cases worth 100% of the total points:
For each test case, output one line containing a single integer: the answer for that test case.
20 1000001 100000
The first test case corresponds to the example given in the problem statement, so the answer is .