We say that X is a subnumber of N if X can be obtained from N by removing some (possibly none) of its digits.
For instance, the subnumbers of 423 are [2, 3, 4, 23, 42, 43, 423], while the subnumbers of 777 are [7, 77, 777].
A number is special if all of its subnumbers are prime. Given an interval [a, b], find how many special numbers it contains.
Input
Two space-separated integers: a and b.
Output
A single integer: the number of special numbers in the interval [a, b].
Constraints
- 1 ≤ a ≤ b ≤ 109
- 1 is not a prime number.
Sample
| Input | Output | Explanation |
|---|---|---|
| 20 30 | 1 | The only special number contained in the interval is 23. |
Let's analyze some properties of constructing special numbers:
- We can only use prime digits: 2, 3, 5, 7.
- We can not use the same digit twice, as it would create a subnumber which is a multiple of 11.
- If we use 2 or 5, they must be the first digit in the number. Otherwise, at least one subnumber would be either even or a multiple of 5.
All of these constraints reduce the search space by a significant amount. From this point on, we can easily generate all special numbers: [2, 3, 5, 7, 23, 37, 53, 73].
The query constraint is what makes this problem tricky, as there is no special number in the interval [74, 109].
