Анике приснился необычный сон. В нем она увидели бесконечную доску. На той доске бесконечно много строк и бесконечно много столбцов, содержащих бесконечно много чисел. Что интересно, каждое число появляется на доске конечное число раз.
Оказывается, доска соответствует вполне понятным рекурсивным правилам. Первая клетка каждой строки содержит номер этой строки (начиная с 1). Значение же в каждой последующей клетке равно сумме значения в предыдущей клетке и перевернутого значения в предыдущей клетке. Перевернутое число можно получить, если записать в обратном порядке цифры десятичного представления числа.
Формально, если
A
(
i
,
j
)
- значение в
i
-й строке и
j
-м столбце доски, то:
1.
A
(
i
, 1) =
i
2.
A
(
i
,
j
) =
A
(
i
,
j
- 1) +
rev
(
A
(
i
,
j
- 1))
, если
j
> 1
.
rev
(
x
)
- операция разворота числа в его десятичном представлении. Например,
rev
(345) = 543
, а
rev
(1040) = 0401 = 401
.
Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа
A
и
B
, а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне
[
A
:
B
]
".
Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.
Примечание
Решения, работающие при
A
,
B
≤ 10
6
, будут оцениваться в 50 баллов.