- Prepare
- Algorithms
- Dynamic Programming
- Lucky Numbers

# Lucky Numbers

# Lucky Numbers

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 .