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

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

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

Формат входных данных

В первой строке ввода дано единственное целое число q — количество запросов (1 ≤ q ≤ 10⁵).

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

Формат выходных данных

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

Пример