Страшные числа

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

Число $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]$.