SPOJ Brasil

Ualter é um garoto muito inteligente, ele ama bastante matemática e qualquer coisa relacionada com números. Recentemente seu amigo Matheus Pheverso mostrou a ele um grupo de números conhecido como H-Números. Este amigo também contou a ele que na Grécia Antiga, esse grupo de números era usado para criar musicas. A descrição matématica dos H-Números é a seguinte:

• Para quaquer inteiro N, um inteiro positivo A só é considerado H-Number em relação a N se e somente se:

  - MMC(N,A) = N * A

• MMC é o Minimo Multiplo Comum entre dois números.

• Ex1: N = 20, H-Números = {1,3,7,9,11,13,17,19}

• Ex2: N = 10, H-Números = {1,3,7,9}

Ualter ama musica classica, principalmente as composições de Pachelbel. Um dos seus sonhos é criar uma musica bonita baseado nos ensinamentos da Grécia Antiga, sendo assim ele está disposto a fazer uma versão de “Canon in D” usando apenas H-Números assim como era feito na Grécia Antiga. Para resolver este problema, ele precisa saber para um dado inteiro N o numero de H-Números de N que estão dentro do intervalo [1,M], inclusivo.

Tarefa

Dado um inteiro Q – a quantidade de queries – e dois numeros N e M em cada query, você deve retornar a quantidade de H-Números de N que estão entre 1 e M, inclusivo.

Entrada

A primeira linha da entrada contém um inteiro Q ( 1 <= Q <= 10⁵ ) representando o número de queries. As próximas Q linhas vão conter cada dois inteiros N e M ( 1 <= N, M <= 10⁵, M < N ).

Saída

Você deve imprimir para cada query um inteiro xi representando o número de H-Números de N que estão no intervalo [1,M], inclusivo.

Exemplo