A estas alturas ya deberías saber qué es un número primo (incluso mi primo lo sabe…) pero, ¿conoces los números invictos? ਐSeguro que no! Decimos que un número es invicto cuando, al borrar los dígitos que no son primos, nos queda un número que sí lo es. ਐQué obsesión los matemáticos y los primos!
En este problema te pedimos que nos digas cuantos números invictos hay de 1 a n.
Entrada
Una secuencia de valores n, cada uno de ellos en una línea.
Salida
Para cada entrada n debes decir cuántos números invictos podemos encontrar en el intervalo [1, n]. Tu programa dispone de 1 segundo de CPU para resolver cada entrada.
Puntuación
Resolver varias entradas con no más de 10 valores n entre 1 y 1000.
Resolver varias entradas con no más de 30000 valores n entre 1 y 1000.
Resolver varias entradas con no más de 10 valores n entre 1 y 106.
Resolver varias entradas con no más de 30000 valores n entre 1 y 106.
Input
1 9 99 999
Output
0 4 52 519