A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between and inclusive, are lucky?
For example, and . Each number is tested below:
digit digit squares
value sum squares sum
20 2 4,0 4
21 3 4,1 5
22 4 4,4 8
23 5 4,9 13
24 6 4,16 20
25 7 4,25 29
We see that two numbers, , and are lucky.
Note: These lucky numbers are not to be confused with Lucky Numbers
Function Description
Complete the luckyNumbers function in the editor below. It should return an integer that represents the number of lucky numbers in the given range.
luckyNumbers has the following parameter(s):
- a: an integer, the lower range bound
- b: an integer, the higher range bound
Input Format
The first line contains the number of test cases .
Each of the next lines contains two space-separated integers, and .
Constraints
Output Format
Output T lines, one for each test case in the order given.
Sample Input
2
1 20
120 130
Sample Output
4
1
Explanation
For the first case, the lucky numbers are , and .
For the second case, the only lucky number is .