시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB32181144.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]$.

예제 입력 1

3
2 10 1
12 15 3
10 20 2

예제 출력 1

4
1
3

예제 입력 2

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

예제 출력 2

4
0
17
12
7