Problema C - Números Olímpicos

A professora O.N.I. (Olga Nunes Ildefonso) gosta muito de todo o tipo de números. Recentemente, interessou-se pelos números que quando são divisíveis por um número primo p, são também divisíveis por p*p. A professora ONI resolveu apelidar de "olimpícos" aos números que apresentassem esta propriedade. Recorda que um primo é um número inteiro positivo maior que um que só é divisível por si próprio e por 1..

Por exemplo, 36 é um número olímpico, pois é divisível pelos primos 2 (mas também por 2*2, pois 36/4=9) e 3 (mas também por 3*3, pois 36/9=4). Já 12 não é olimpíco, uma vez que é divisível pelo primo 3, mas não por 3*3.

A professora ONI está neste momento a calcular todos os números olímpicos e precisa da tua ajuda.

O Problema

Input

Na primeira linha de input vem um número inteiro C, indicando o número de casos a considerar (1≤C≤10).

Seguem-se exactamente C linhas, cada uma contendo apenas dois números inteiros INF e SUP, separados por um espaço, indicando respectivamente o limite inferior e superior do intervalo a considerar. É garantido que 1≤INF≤SUP<2^31.

Output

O output é constituído por C linhas, uma para cada caso de input. Cada uma dessas linhas deve conter um único número, indicando quantos números olimpícos existem no intervalo [INF,SUP], ou seja, maiores ou iguais a INF e menores ou iguais a SUP.

Exemplo de Input

3
1 4
1 20
10 20

Exemplo de Output

2
5
1