|
ACM - Universidad Autonoma de Puebla |
Un primo está definido como un número entero positivo que únicamente es divisible por la unidad y por sí mismo (para este problema consideraremos a la unidad también como primo). Existen primos especiales, como es el caso de los primos rellenos.
Un número primo n formado de m digitos (n1n2…nm) se dice relleno si los números formados de los siguientes digitos: n1, n1n2, n1n2n3, …, n1n2…nm son todos primos.
El problema consiste en decir cuántos primos rellenos distintos entre sí existen entre ini y fin (incluyéndolos), donde 1 ≤ ini ≤ fin ≤ 100,000,000.
La primera línea de la entrada consiste de un entero t (1 ≤ t ≤100) que indica el número de casos a procesar. Cada caso consiste de una línea con los valores de ini y fin (1 ≤ ini ≤ fin ≤ 100,000,000);
Por cada caso imprime un número k que indica el total de primos rellenos que existen entre ini y fin (incluyéndolos).
Ejemplo de entrada |
Ejemplo de salida |
|---|---|
3 |
42 |