Prime Qualification

Farmer John is numbering his cows one by one with prime numbers. Bessie became curious about how often the digit $D$ shows up among these numbers.

Help Bessie count how many prime numbers in the range from $A$ to $B$ (inclusive) contain the digit $D$ in their decimal representation.

A prime is a natural number greater than 1 whose only divisors are 1 and itself. The first few primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$.

Three integers $A$, $B$, and $D$ are given on one line, separated by spaces. Here $D$ is a single decimal digit (from $0$ to $9$).

Print, on one line, the number of primes within the given range that contain the digit $D$.

• $1 \le A \le B \le 4{,}000{,}000$
• $B \le A + 2{,}000{,}000$

For example, the primes in the range from $10$ to $15$ are $11$ and $13$, and only $13$ contains the digit $3$.