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
11
65 0
269 1
312 2
745 3
1457 4
1686 5
1882 6
4270 7
6242 8
9838 9
9868 10
Sample Output
43
7341
9651
46264
167332
226094
278015
1218448
2443417
5802272
5851533
Explanation
For the first one, the only integers less than for which is a square are and , hence the answer is 43.