Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2767.   Qualified Primes
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 1926   Accepted Runs: 444    Multiple test files

Farmer John has begun branding the cows with sequential prime numbers. Bessie has noticed this and is curious about the occurrence of various digits in those brands.

Help Bessie determine the number of primes in the inclusive range A..B (1 ≤ AB ≤ 4,000,000; BA + 1,000,000; one test case has BA + 2,000,000 ) that contain a supplied digit D.

A prime is a positive integer with exactly two divisors (1 and itself). The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and, 29.

Input

* Line 1: Three space-separated integers: A, B, and D

Output

* Line 1: The count of primes in the range that contain the digit D.

Sample Input

10 15 3


Sample Output

1


Input Details

How many primes in the range 10..15 contain the digit 3?

Output Details

Just 13 in this range contains a '3'.

Source: USACO 2007 January Competition
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz