Project Euler #211: Divisor Square Sum

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

For a positive integer , let be the sum of the squares of its divisors. For example,

You are given two integers and , you need to find the sum of all such that is at most away from a perfect square.

Input Format

The first line of each test file contains a single integer which is the number of queries.
Each of the next lines contains two space-separated integers, and .

Constraints

Output Format

Print the answer to each query in a new line.

Sample Input

Sample Output

Explanation

For the first one, the only integers less than for which is a square are and , hence the answer is 43.