Число є красивим, якщо воно має рівно \(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