Prime Suffixes

Time limit1sMemory limit512 MB

Summary

Count numbers in [a, b] whose decimal digits contain no zero and whose every suffix is prime.

Level: Medium7 of 10
Topics: Number theory, Brute force, Recursion, Math
Solved: No attempts yet

Statement

We call a number $y$ a suffix of a number $x$ if we can remove digits from the beginning of the decimal representation of $x$ to get $y$ . If the decimal representation of $x$ has no zeroes, none of the suffixes of $x$ has a leading zero. For example, the suffixes of $283$ are $283$ , $83$ , and $3$ .

An integer is prime if it has exactly two positive integer divisors. The number $1$ is not prime: it has only one positive integer divisor.

Senya likes prime numbers that have no zeroes in their decimal representation and whose every suffix is also prime.

You are given integers $a$ and $b$ . Help Senya find how many integers between $a$ and $b$ he likes.

Input

The input contains two integers $a$ and $b$ ( $1 \le a \le b \le 10^{11}$ ).

Output

Print the number of primes between $a$ and $b$ inclusive such that they have no zeroes in their decimal representation, and if any number of their leading digits are removed, the resulting number is still prime.

Notes

In the first example, Senya likes the integers $5$ , $7$ , and $13$ .

In the second example, every integer in the range has a $0$ in its decimal representation.

In the third example, Senya likes the integer $283$ , since $283$ , $83$ , and $3$ are all prime.

Examples3

Example 1
Input
```
4 13
```
Expected output
```
3
```
Example 2
Input
```
101 109
```
Expected output
```
0
```
Example 3
Input
```
281 286
```
Expected output
```
1
```