- All Contests
- ProjectEuler+
- Project Euler #141: Investigating progressive numbers, n, which are also square.

# Project Euler #141: Investigating progressive numbers, n, which are also square.

# Project Euler #141: Investigating progressive numbers, n, which are also square.

_{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 .