该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
这是这个问题的困难版本，两个版本的不同之处在于数据范围不同
定义f(x)为：
$$f(x)=
\left\{\begin{matrix}
\left ( x \mod 10 \right ) \cdot f(\left \lfloor \frac{x}{10} \right \rfloor )& x\ge 10 \\
x & x<10
\end{matrix}\right.\\
$$
⌊10x⌋ 表示x除以10下取整的结果
xmod10 表示x对10取余的结果
素数集合可以用数学符号表示为 P 或 Prime
$$
\mathbb{P} = \{ p \in \mathbb{Z}^+ \mid p \text{ 是素数} \}
$$
你已知两个正整数L和R，请计算
i=L∑R[f(i)∈P]
换句话说，求L到R中有多少数在经过f函数的计算后的结果为质数
输入格式
第一行包含一个整数 T(1≤T≤105)—测试用例的数量。
一行输入包含两个正整数L和R，(1≤L≤R≤109)
输出格式
输出T行，每行一个整数，表示你所计算的答案
样例
3
1 10
1 100
1 200
4
12
20
第三个样例满足的数如下
$[
2,3,5,7,12,13,15,17,21,31,51,71,112,113,115,117,121,131,151,171
]$
