410618: GYM104066 A Страшные числа

A. Страшные числаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Все мы, конечно же, очень любим числа, а также задачи на математику! Но, говорят, в Хэллоуин все задачи на математику становятся гораздо более страшными... Сегодня вашей задачей будет посчитать количество страшных чисел!

Число $$$x$$$ называется $$$k$$$-страшным, если количество множителей в его разложении на простые числа равно $$$k$$$. Пока что, возможно, вам не кажется страшным такое определение, но вы еще не видели, в чем заключается вопрос задачи!

Требуется ответить на $$$q$$$ запросов, каждый из которых описывается тремя целыми числами $$$l$$$, $$$r$$$ и $$$k$$$. Ответом на запрос является количество $$$k$$$-страшных чисел, лежащих на отрезке от $$$l$$$ до $$$r$$$. Если вас все еще не пугает эта задача, ответьте на все $$$q$$$ запросов.

Входные данные

В первой строке ввода дано единственное целое число $$$q$$$ — количество запросов ($$$1 \leqslant q \leqslant 10^5$$$).

В $$$i$$$-й из следующих $$$q$$$ строк через пробел записаны три натуральных числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ — параметры запроса (границы отрезка и $$$k$$$ из определения $$$k$$$-страшного числа) ($$$2 \leqslant l_i \leqslant r_i \leqslant 10^5$$$; $$$1 \leqslant k \leqslant 16$$$).

Выходные данные

Для $$$i$$$-го запроса выведите в отдельной строке количество $$$k_i$$$-страшных чисел на отрезке $$$[l_i, r_i]$$$.

ПримерыВходные данные

3
2 10 1
12 15 3
10 20 2

Выходные данные

4
1
3

Входные данные

5
21 40 1
46 65 9
50 100 2
100 150 3
150 200 4

Выходные данные

4
0
17
12
7