#P2405. 数字

    ID: 1450 传统题 1000ms 128MiB 尝试: 309 已通过: 138 难度: 5 上传者: 标签>CF1700普及+/提高-模意义不变量最小公倍数暴力枚举一维前缀和

数字

题目描述

小 D 喜欢的数有这样的性质: 令 nn为正整数,S⁡(n)\operatorname{S}(n)为 nn 的各位数字之和,令

$$\operatorname{D}(n) = \left\{ \begin{aligned} & \operatorname{S}(n) , & \operatorname{S}(n) < 10\\ & \operatorname{D}(\operatorname{S}(n)) , &\operatorname{S}(n)\ge 10\\ \end{aligned} \right.$$

小 D 喜欢的数一定能表示成 x×D⁡(x)x \times \operatorname{D}(x) 这种形式。(即若一个数 AA 是被喜欢的,则存在一个正整数 xx ,使得 A=x×D⁡(x)A = x \times \operatorname{D}(x) )

小 D 想知道在区间 [L,R][L , R] 中,有多少个数是他喜欢的。

输入格式

第一行一个整数 TT ,表示数据组数。

以下每一行两个整数 L,RL,R ,代表询问 [L,R][L, R] 。

输出格式

输出 TT 行,每行一个整数,表示在这个区间内小 D 喜欢的数出现了多少次。

3
1 5
3 9
8 8
2
2
0

数据规模与约定

对于 100%100\% 的数据,保证 1≤L≤R≤1018,T≤201\le L\le R \le 10^{18} , T\le 20 。