Criptografia

Um dos passos na geração de chaves privadas e públicas no algoritmo RSA é a escolha de dois números primos grandes, $p$ e $q$. A partir desses números, calcula-se $n=p\cdot q$ e realizam-se uma série de operações sobre $n$ para gerar as chaves. A segurança do método depende da dificuldade de fatorar $n$ em seus fatores primos $p$ e $q$. Os números que são produtos de dois primos são conhecidos como semiprimos.

Você, como aspirante a criptógrafo, decidiu estudar a dificuldade de fatoração de números grandes e a distribuição de números semiprimos. Para isso, você quer escrever um programa que determine quantos números semiprimos existem em um intervalo $[l,r]$ dos naturais.

Entrada

A primeira linha da entrada descreve um inteiro $n$ ($1 < n \leq 10^{5}$), que é o número de consultas a serem respondidas. As próximas $n$ linhas, descrevem, cada uma, o intervalo da consulta por meio de dois inteiros, $l$ e $r$ ($1\leq l\leq r \leq 10^7$).

Saída

Imprima, para cada consulta, o número de números semiprimos no intervalo $[l,r]$.

Notas

Existem $4$ semiprimos no intervalo $[1,10]$, que são: $4$, $6$, $9$ e $10$.

Existem $3$ semiprimos no intervalo $[10,20]$, que são: $10$, $14$ e $15$.

Finalmente, existem $4$ semiprimos no intervalo $[20,30]$, que são: $21$, $22$, $25$ e $26$.

3
1 10
10 20
20 30

4
3
4