- All Contests
- ProjectEuler+
- Project Euler #125: Palindromic sums

# Project Euler #125: Palindromic sums

# Project Euler #125: Palindromic sums

_{This problem is a programming version of Problem 125 from projecteuler.net}

A *palindromic number* has the same digits from left to right as it does from right to left.

The palindromic number is interesting because it can be written as the sum of consecutive squares: .

The palindromic number is also nice because it can be written as , where the bases form an arithmetic progression with common difference .

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is . Note that has not been included as this problem is concerned with the squares of positive integers. Also, there has to be at least two terms in the sum.

Given and , find the sum of all the numbers less than that are both palindromic and can be written as the sum of squares whose bases form an arithmetic progression with common difference .

**Input Format**

The first line of input contains , the number of test cases.

Each test case consists of a single line containing two integers and , separated by a space.

**Constraints**

**Output Format**

For each test case, output a single line containing a single integer, the answer for that test case.

**Sample Input**

```
2
1000 1
1000 2
```

**Sample Output**

```
4164
3795
```

**Explanation**

The first test case corresponds to the example given in the problem statement.

In the second test case, , and there are such numbers less than . Two such numbers are: