Problema A - Uma Questão de Divisores

A Ana e o Aniceto, dois grandes amigos, gostam muito de tudo o que envolve matemática. Recentemente, estavam a jogar um novo jogo que consistia em descobrir muito rapidamente quantos divisores tem um dado número inteiro positivo. Um divisor é um número inteiro positivo que divide exactamente outro número inteiro positivo, ou seja, d é divisor de n se existir um inteiro q tal que d vezes q é igual a n. Por exemplo, o número 10 tem exactamente 4 divisores (1, 2, 5 e o próprio 10).

Uma vez que são muito rápidos nos cálculos, resolveram complicar um pouco mais o jogo, para o tornar mais desafiante. Em vez de apenas dizerem quantos divisores tem um dado número, têm de dizer quantos números dum dado intervalo têm uma determinada quantidade de divisores. Por exemplo, o jogo pode consistir em dizer rapidamente quantos números entre 1 e 15 têm exactamente 4 divisores. Neste caso a resposta seria 5, pois existem 5 números entre 1 e 15 que têm 4 divisores: 6, 8, 10, 14 e 15.

                 Número:   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Quantidade de divisores:   1   2   2   3   2   4   2   4   3   4   2   6   2   4   4

Depois de seleccionarem previamente a quantidade de divisores, a Ana e o Aniceto definem os intervalos que lhes interessam. O jogo consiste em repetidamente um deles ir definindo um novo intervalo de números e o outro ir respondendo quantos números nesse intervalo têm a quantidade pretendida de divisores.

Tens de ajudar a Ana e o Aniceto fazendo um programa para jogar este jogo!

O Problema

Dado um número D (a quantidade de divisores), N pares de números A_i e B_i, a tua tarefa é descobrir para cada um destes pares quantos números entre A_i e B_i (inclusive, ou seja, no intervalo [A_i,B_i]) têm exactamente D divisores.

Input

Na primeira linha do input vem um único número inteiro D indicando a quantidade de divisores a considerar. Na segunda linha vem um número inteiro N indicando o número de intervalos a considerar.

Seguem-se exactamente N linhas, cada uma contendo exactamente dois números inteiros separados por um espaço: A_i e B_i, indicando que deves considerar números entre esses limites. Os limites do intervalo pertencem ao intervalo.

Output

O output deve ser constituído exactamente por N linhas, cada uma contendo um único número inteiro indicando a quantidade de números no intervalo [A_i,B_i] que têm exactamente D divisores. Estas linhas devem vir pela mesma ordem em que os intervalos aparecem no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos é inferior a 10 e quer a quantidade de divisores, quer os números que limitam o intervalo, são inferiores 1000.

Exemplo de Input

4
5
1 10
1 15
11 15
1 5
20 30

Exemplo de Output

3
5
2
0
4