beautiful number

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Let $A = \sum_{i=1}^{n}a_i * {10}^{n-i}(1\leq a_i \leq 9)$($n$ is the number of $A$'s digits). We call $A$ as “beautiful number” if and only if $a[i] \geq a[i+1]$ when $1 \leq i<n$ and $a[i]$ mod $a[j]=0$ when $1 \leq i \leq n,i<j \leq n$(Such as 931 is a "beautiful number" while 87 isn't).
Could you tell me the number of “beautiful number” in the interval $[L,R]$(including L and R)?

Input

The fist line contains a single integer $T$(about 100), indicating the number of cases.
Each test case begins with two integers $L,R(1 \leq L \leq R \leq {10}^{9})$.

Output

For each case, output an integer means the number of “beautiful number”.

Sample Input

2 1 11 999999993 999999999

Sample Output

10 2

Hint

hujie

Source

BestCoder Round #31

提交代码