G. D-Функция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$D(n)$$$ представляет собой сумму цифр числа $$$n$$$. Для скольких целых чисел $$$n$$$, $$$10^{l} \leq n < 10^{r}$$$, выполняется условие $$$D(k \cdot n) = k \cdot D(n)$$$? Выведите ответ по модулю $$$10^9+7$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Каждый набор содержит три целых числа $$$l$$$, $$$r$$$ и $$$k$$$ ($$$0 \leq l < r \leq 10^9$$$, $$$1 \leq k \leq 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите целое число — ответ, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1
Выходные данные
2
3
90
12
974995667
999
Примечание

Для первого примера единственные значения $$$n$$$, удовлетворяющие условию, — это $$$1$$$ и $$$2$$$.

Для второго примера единственные значения $$$n$$$, удовлетворяющие условию, — это $$$1$$$, $$$10$$$ и $$$11$$$.

Для третьего примера все значения $$$n$$$ от $$$10$$$ включительно до $$$100$$$ исключительно удовлетворяют условию.