题目描述

小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喜欢的数出现了多少次。

输入样例

3
1 5
3 9
8 8

输出样例

2
2
0

提示

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。