Prime Qualification

Time limit2sMemory limit128 MB

Summary

Count primes between A and B whose decimal representation contains the digit D.

Level: Easy3 of 10
Topics: Number theory, Math, Implementation, Brute force
Solved: No attempts yet

Problem

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$ .

Input

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$ ).

Output

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

Constraints

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

Hint

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

Examples3

Example 1
Input
```
10 15 3
```
Expected output
```
1
```
Example 2
Input
```
2 2 2
```
Expected output
```
1
```
Example 3
Input
```
1 30 1
```
Expected output
```
4
```