/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正整数からなる集合 A は次の条件を満たすとき、良い集合であるといいます。
- 任意の相異なる 2 要素 a, b \in A に対して、a を 10 進法表記した文字列は、b を 10 進法表記した文字列の部分文字列ではない。
部分文字列とは？
部分文字列とは連続する部分列のことを指します。例えば1, 12, 23 は 123 の部分文字列ですが、21 や 13 は 123 の部分文字列ではありません。
正整数 L, R が与えられます。L 以上 R 以下の整数からなる良い集合 A の要素数の最大値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T\leq 10^4
- 1\leq L\leq R\leq 10^{9}
入力
入力は以下の形式で標準入力から与えられます。
T
\text{case}_1
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます。
L R
出力
T 行出力してください。i 行目には、\text{case}_i に対する答えを出力してください。
入力例 1
3 3 8 3 18 1 1000
出力例 1
6 10 900
はじめの 2 つのテストケースについて、例えば次の A が要素数が最大であるような良い集合となります。
- 1 つめのテストケース：A=\{3,4,5,6,7,8\}.
- 2 つめのテストケース：A=\{3,4,6,8,9,10,11,12,15,17\}.
Score : 400 points
Problem Statement
A set A of positive integers is said to be good when it satisfies the following condition.
- For any two distinct elements a, b \in A, the string representing a in base ten is not a substring of the string representing b in base ten.
What is a substring?
A substring of a string is its contiguous subsequence. For example,1, 12, and 23 are substrings of 123, while 21 and 13 are not.
You are given positive integers L and R. Find the maximum possible number of elements in a good set A consisting of integers between L and R (inclusive).
We will give you T test cases; solve each of them.
Constraints
- 1\leq T\leq 10^4
- 1\leq L\leq R\leq 10^{9}
Input
Input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each case is in the following format:
L R
Output
Print T lines. The i-th line should contain the answer for \text{case}_i.
Sample Input 1
3 3 8 3 18 1 1000
Sample Output 1
6 10 900
For the first two cases, the following are good sets A with the maximum number of elements.
- Case 1: A=\{3,4,5,6,7,8\}.
- Case 2: A=\{3,4,6,8,9,10,11,12,15,17\}.