Все мы, конечно же, очень любим числа, а также задачи на математику! Но, говорят, в Хэллоуин все задачи на математику становятся гораздо более страшными... Сегодня вашей задачей будет посчитать количество страшных чисел!
Число $$$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