题目描述

这是这个问题的困难版本，两个版本的不同之处在于数据范围不同
定义$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.\\ $$

$\left \lfloor \frac{x}{10} \right \rfloor$ 表示$x$除以$10$下取整的结果

$x \mod 10$ 表示$x$对$10$取余的结果

素数集合可以用数学符号表示为 $\mathbb{P}$ 或 $Prime$

$$ \mathbb{P} = \{ p \in \mathbb{Z}^+ \mid p \text{ 是素数} \} $$

你已知两个正整数$L$和$R$，请计算

$$\sum_{i=L}^{R} [f(i) \in \mathbb{P}]$$

换句话说，求$L$到$R$中有多少数在经过$f$函数的计算后的结果为质数

输入格式

第一行包含一个整数 $T (1≤T≤{\color{Red} 10^{5}})$—测试用例的数量。
一行输入包含两个正整数$L$和$R$，$(1 \le L \le R \le {\color{Red} 10^{9}})$

输出格式

输出$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 ]$