F. Минимальная разница подмножеств
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будем называть положительное целое число x k-красивым целым числом, если и только если возможно разбить мультимножество его цифр в десятичном представлении на два подмножества так, чтобы разница между суммой цифр в этих множествах была меньше либо равна k. Каждая цифра должна принадлежать ровно одному подмножеству послу разбиения.

Мы подготовили для вас n запросов. Каждый запрос описывается тремя целыми числами l, r и k, которые означают, что вы должны вычислить количество k-красивых целых чисел x в пределах от l до r (включительно).

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

Первая строка содержит одно целое число n (1 ≤ n ≤ 5·104) — количество запросов.

Каждая из следующих n строк описывает один запрос и содержит три целых числа l, r и k (1 ≤ l ≤ r ≤ 1018, 0 ≤ k ≤ 9).

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

Для каждого запроса выведите одно целое число — ответ на этот запрос.

Примеры
Входные данные
10
1 100 0
1 100 1
1 100 2
1 100 3
1 100 4
1 100 5
1 100 6
1 100 7
1 100 8
1 100 9
Выходные данные
9
28
44
58
70
80
88
94
98
100
Входные данные
10
1 1000 0
1 1000 1
1 1000 2
1 1000 3
1 1000 4
1 1000 5
1 1000 6
1 1000 7
1 1000 8
1 1000 9
Выходные данные
135
380
573
721
830
906
955
983
996
1000
Примечание

Если 1 ≤ x ≤ 9, то число x является k-красивым если и только если x ≤ k.

Если 10 ≤ x ≤ 99, то число x = 10a + b является k-красивым если и только если |a - b| ≤ k, где a и b — целые числа от 0 до 9 включительно.

100 является k-красивым только и только если k ≥ 1.