2017 Asia HCMC Vietnam National Programming Contest

Start

2017-11-05 01:00 UTC

2017 Asia HCMC Vietnam National Programming Contest

End

2017-11-05 06:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -400 days 11:51:01

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