Copiado al portapapeles
Descripción
Paterson era un estudiante de 15 años cuando le contaron que si uno hallaba un numero primo muy grande podía ganar dinero tuvo la idea de que los números en base 4 interpretados en base decimal también son primos. Cuando hizo la tabla que se muestra pensó que estaba en lo cierto.
Numero Primo Numero en base 4 2 2 3 3 5 11 7 13 11 23 13 31 17 101
Como ve la interpretación en base 4 como decimal también es primo.
El numero primo 31 es el primero que falla, y de allí en adelante para algunos falla:
Numero Primo Numero en base 4 31 133 = 7x19 41 221 = 13x17 59 323 = 17x19
Entrada
La entrada comienza con un numero $(1 \leq n \leq 1000)$ el numero de casos de prueba.
Luego siguen $n$ líneas con dos números $(2 \leq a \leq b \leq 10000)$.
Salida
Por cada caso de prueba escriba la cantidad de números en los que falla la teoría de Paterson.
Ejemplo Entrada
3 2 17 2 41 31 59
Ejemplo Salida
0 2 3