Contest Duration: - (local time) (180 minutes) Back to Home
A - Antichain of Integer Strings /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 任意の相異なる 2 要素 a, b \in A に対して、a10 進法表記した文字列は、b10 進法表記した文字列の部分文字列ではない

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\}.