| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 32 | 18 | 11 | 44.000% |
Все мы, конечно же, очень любим числа, а также задачи на математику! Но, говорят, в Хэллоуин все задачи на математику становятся гораздо более страшными... Сегодня вашей задачей будет посчитать количество страшных чисел!
Число $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