题目描述

我们称一个正整数为“classy”，当且仅当它的十进制表示中存在不超过 $3$ 个的非零数字。

例如，数字 $4$、$200000$、$10203$ 是“classy”的，而 $4231$、$102306$、$7277420000$ 不是。

给定一个区间 $[L, R]$，请统计有多少个“classy”整数 $x$ 满足 $L \leq x \leq R$。

每个测试用例包含若干个区间，对于每个区间你都需要分别解决这个问题。

输入格式

第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示本测试用例中区间的个数。

接下来的 $T$ 行，每行包含两个整数 $L_i$ 和 $R_i$（$1 \leq L_i \leq R_i \leq 10^{18}$）。

输出格式

输出 $T$ 行，第 $i$ 行输出区间 $[L_i, R_i]$ 内“classy”整数的个数。

说明/提示

由 ChatGPT 4.1 翻译

样例

4
1 1000
1024 1024
65536 65536
999999 1000001

1000
1
0
2