Problem C
Subprime

Image by Marina Shemesh

There is an open math problem: Is every non-negative integer a substring of at least one prime number when expressed in base ten?

A positive integer is a prime number if it is greater than one and not a product of two smaller positive integers. Integer $a$ is a substring of integer $b$ if it is equal to an integer derived from $b$ by deleting zero or more consecutive digits of the most and least significant digits of $b$. For example, $123$ is a substring of: $\underline{123}, 56\underline{123}, \underline{123}789, 501823\underline{123}65, 4\underline{123}7912\underline{123}$.

Given two integers $l$ and $h$ along with an integer $p$, you are to check how many primes between the $l$th smallest prime and the $h$th smallest prime (both ends are inclusive) contain a substring that equals $p$. We are interested in substrings that may include significant leading zeroes, and thus $p$ may have leading zeroes. A prime shall be counted only once even if the integer $p$ occurs more than once as its substring.

For example, consider $l = 1, h = 10$ and $p = 9$. This is a search from the $1$st smallest prime ($2$) to the $10$th smallest prime ($29$) for any prime containing the substring “$9$”. There are $2$ such primes: $1\underline{9}$ and $2\underline{9}$.

Input

The first line of input has two integers $l$ and $h$ ($1 \leq l \leq h \leq 10^5$). The second line has a sequence of $1$ to $6$ digits giving the integer $p$, which may be zero or have significant leading zeroes.

Output

Output the count of prime numbers in the given range that contain $p$ as a substring.

1 10
9

2

500 1000
43

26

1 1000
00

10