Rick quiere ir a jugar con sus amigos lo mas antes posible, pero en la escuela le dejaron tarea de matemáticas, lo cual consiste de los siguiente:

Se te dara un intervalo de números enteros $L$ y $R$, la tarea de Rick es sumar los números primos que se encuentran en ese intervalo, parece una tarea sencilla, pero mientras el intervalo es mas grande se hace mas dificil resolver.

Rick se entero que tu eres un programador, asi que pide tu ayuda para resolver su tarea.

La primera linea consiste de un entero $q$, $(1 \leq q \leq 10 ^ 5)$ la cantidad de casos de prueba.

Luego vienen $q$ lineas, la linea $q_i$, tiene dos números enteros $L_i$ y $R_i$, $(1 \leq L_i \leq R_i \leq 10 ^ 5)$

Para cada caso de prueba imprima la suma de números primos en el intervalo pedido.