NTU VNPC-2017 Replay

Start

2018-05-11 04:30 UTC

NTU VNPC-2017 Replay

End

2018-05-11 09:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -377 days 6:27:29

Time elapsed

5:00:00

Time remaining

0:00:00

Problem I
Integer Rotation

An integer $m$ is a rotated number of some integer $n$ if $m$ can be obtained by moving some digits from the back of $n$ to the front without changing their order. In this case, $(n,m)$ is considered as a rotated pair. For example, $(1234,4123)$ is a rotated pair since you can obtain $4123$ by moving $4$ from the back of $1234$ to the front. Note that both $n$ and $m$ do not contain leading zeros.

Given two integers $A$ and $B$, your task is to count the number of distinct rotated pairs $(n,m)$ with ${A \leq n < m \leq B}$.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is not greater than $100$. The following lines describe the datasets.

Each dataset is printed in one line containing two integers $A$ and $B$ (${1 \leq A < B \leq 10^6}$).

Output

For each dataset, write out on one line the number of rotated pairs.

Sample Input 1 Sample Output 1
2
1 10
10 50
0
6