题目描述

译自 ROI Regional 2025 Day1 T2. Простоватые числа

我们将一个数称为质乘数，当且仅当它的十进制数字的乘积是一个质数。例如，$12$ 是质乘数，而 $29$ 则不是。

你的任务是计算从 $l$ 到 $r$（包括 $l$ 和 $r$）之间的质乘数的数量。

若一个整数 $p > 1$，并且它只有两个正整数因数：$1$ 和 $p$，那么称 $p$ 为质数。

输入格式

第一行包含一个整数 $l$ ($1 \leq l \leq 10^{100\,000}$)

第二行包含一个整数 $r$ ($l \leq r \leq 10^{100\,000}$)

请注意，这些数字的长度超出了大多数编程语言的标准整数类型范围，特别是在 C++ 中。因此，需要以特殊的方式读取输入，例如将其作为字符串读取。

输出格式

输出从 $l$ 到 $r$ 之间质乘数的数量。

样例

输入

42
179

输出

10

数据范围与提示

详细子任务附加限制及分值如下表所示。