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: