B. Простоватые числа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём число простоватым, если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 12, а число 29 не является.

Требуется посчитать количество простоватых чисел от $$$l$$$ до $$$r$$$.

Напомним, что целое число $$$p \gt 1$$$ называется простым, если оно имеет ровно два делителя: $$$1$$$ и $$$p$$$.

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

Первая строка содержит одно целое число $$$l$$$ ($$$1 \le l \le 10^{100\,000}$$$).

Вторая строка содержит одно целое число $$$r$$$ ($$$l \le r \le 10^{100\,000}$$$).

Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки.

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

Выведите количество простоватых чисел от $$$l$$$ до $$$r$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

|c|c|}

Подзадача

Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
119 $$$1 \le l \le r \le 10^6$$$первая ошибка
226 $$$1 \le l \le r \le 10^{18}$$$1первая ошибка
312 $$$l = 1$$$, $$$r = 10^{k}$$$, где $$$k$$$ ($$$1 \le k \le 10^5$$$)первая ошибка
418 $$$1 \le l \le r \le 10^{1000}$$$1, 2первая ошибка
525 —1–4первая ошибка
Пример
Входные данные
42
179
Выходные данные
10