区间计数 - ROJ

小D喜欢的数有这样的性质：令 $n$ 为正整数， $S(n)$ 为 $n$ 的各位数字之和，令

D(n) = \begin{cases}S(n),S(n)<10\\D(S(n)),S(n)≥10\\ \end{cases}

若一个数能表示成

x×d(x)

这种形式，则这个数是小D喜欢的。小D想知道在区间

[L,R]

中，有多少个数是他喜欢的。

有多组数据。第一行一个整数 $T$ ，表示数据组数。以下每一行两个数 $L$ 、 $R$ （保证区间合法），代表询问 $[L,R]$ 。

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

2
2
0

【数据规模】对于30%的数据， $L,R≤10^6$ ；对于100%的数据， $T≤20，L,R≤10^{18}$ 。