Truncatable Primes

Time limit1sMemory limit512 MB

Summary

Count integers in [a, b] whose every prefix from the left is prime.

Level: Medium7 of 10
Topics: Backtracking, Number theory
Solved: No attempts yet

Problem

Recall that a prime is a positive integer with exactly two distinct divisors: $1$ and itself. We say that a number $a$ is a prefix of a number $b$ if $a$ can be obtained by deleting some number of digits from the end of $b$ . For example, $1231$ is a prefix of $12314433$ . A truncatable prime is a number all of whose prefixes of non-zero length are prime. For example, $23$ is a truncatable prime, because its non-empty prefixes $2$ and $23$ are both prime.

Given two positive integers $a$ , $b$ ( $a \le b$ ), write a program that determines how many integers in the closed interval $[a, b]$ are truncatable primes.

Input

A single line of standard input contains two integers $a$ , $b$ ( $1 \le a \le b \le 10^{18}$ ), separated by a space.

Output

Print a single integer: the number of truncatable primes that are not less than $a$ and not greater than $b$ .

Hint

There are only finitely many such numbers. The first digit must be one of the single-digit primes $2$ , $3$ , $5$ , $7$ , and every time you append a digit on the right the resulting number must still be prime. So you can generate all such numbers in advance and then count those that fall inside the interval.

Examples3

Example 1
Input
```
20 24
```
Expected output
```
1
```
Example 2
Input
```
1 10
```
Expected output
```
4
```
Example 3
Input
```
1 1000000000000000000
```
Expected output
```
83
```