Números invictos P65824

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

• Test1:  ‍40 Puntos ‍

  Resolver varias entradas con no más de 10 valores n entre 1 y 1000.

• Test2:  ‍20 Puntos ‍

  Resolver varias entradas con no más de 30000 valores n entre 1 y 1000.

• Test3:  ‍30 Puntos ‍

  Resolver varias entradas con no más de 10 valores n entre 1 y 10⁶.

• Test4:  ‍10 Puntos ‍

  Resolver varias entradas con no más de 30000 valores n entre 1 y 10⁶.