Назовём число простоватым, если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 12, а число 29 не является.
Требуется посчитать количество простоватых чисел от \(l\) до \(r\).
Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).
Формат входных данных
Первая строка содержит одно целое число \(l\) (\(1 \le l \le 10^{100\,000}\)).
Вторая строка содержит одно целое число \(r\) (\(l \le r \le 10^{100\,000}\)).
Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки.
Формат выходных данных
Выведите количество простоватых чисел от \(l\) до \(r\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
42
179
|
10
|