Reyno recently realized that his birth year, , has a special property: no digit of is equal to zero and each suffix of is prime. He has decided to call any number with this property a superprime. Now, he wonders how often superprimes occur.
Given an integer , can you compute the number of superprimes less than ?
Input Specification
The first line of input contains a single integer .
For of the points, .
For of the points, .
Output Specification
The number of superprimes less than .
Sample Input 1
10
Sample Output 1
4
Sample Input 2
100
Sample Output 2
15
Comments
Clues please? I was thinking of using sieve of eratosthenes, but N<=10^18, and just checking if each one is a superprime will obviously TLE