Число є красивим, якщо воно має рівно $k$ дільників.

Знайдіть відповідь до $q$ запитів. Кожен запит складається з двох чисел $l$ та $r$, відповіддю на запит є кількість красивих чисел серед $l,l+1,\dots ,r$.

Input Specification

У першому рядку вхідного файлу розміщено два цілі числа $k$ ($1\le k\le 100$) та $q$ ($1\le q\le 5\cdot {10}^5$).

У кожному з наступних $q$ рядків розміщені 2 цілі числа $l$ та $r$ ($1\le l\le r\le {10}^6$).

Output Specification

Для кожного запиту виведіть відповідь в новому рядку.

Sample Input 1

4 3
1 10
5 9
3 20

Sample Output 1

3
2
5