El granjero Juan hoy está muy contento porque descubrió que existen números que tienen solamente dos divisores: 1 y el propio número. Juan desea conocer la cantidad de números que cumplen esta condición para ~N~ intervalos ~[A, B]~.

Entrada

• Línea 1: Un entero ~N~ ~(1 \leq N \leq 30)~ que representa la cantidad de intervalos.
• Líneas 2...N+1: Dos números por línea ~A~ y ~B~, ~(1 \leq A \leq B \leq 1000,000)~ que representan los límites del intervalo.

Ejemplo de Entrada

2 
1 10 
50 53

Detalles de la Entrada: Dos intervalos. El primer intervalo está limitado por ~1~ y ~10~ y el segundo intervalo está limitado por ~50~ y ~53~.

Salida

• Línea 1…N: La salida estará compuesta por ~N~ líneas. Cada línea representará un entero con la respuesta del problema para el intervalo ~i~.

Ejemplo de Salida

4 
1

Detalles de la Salida: En el primer intervalo existen 4 números que cumplen las condiciones del problema: ~2, 3, 5~ y ~7~. En el segundo caso, el único número que satisface las condiciones del problema es el ~53~.