D. Красивые числа
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Володя странноват, как, впрочем, и его вкусы. Он считает натуральное число красивым в том и только в том случае, когда оно делится на любую свою ненулевую цифру. Мы не будем спорить с Володей, лучше посчитаем количество красивых чисел в заданном интервале.

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

Первая строка входных данных содержит количество тестов t (1 ≤ t ≤ 10). Каждая из последующих t строк содержит два натуральных числа li и ri (1 ≤ li ≤ ri ≤ 9 ·1018).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).

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

Выведите t чисел, каждое на своей строке, — ответы на запросы, то есть в i-й строке — количество красивых чисел от li до ri включительно.

Примеры
Входные данные
1
1 9
Выходные данные
9
Входные данные
1
12 15
Выходные данные
2