Let denote the count of digits of a number in its decimal representation.
John is looking for new methods of determining which numbers are strange all day long.
All non-negative numbers of length 1 are strange. Further, a number with can also be considered strange if and only if

• is evenly divisible by
• the number is recursively strange

Your task is to calculate how many strange numbers belong to an interval .

Input Format
The first line contains single integer - the number of test cases. Next lines contain two integers separated by single space and .

Output Format
In lines, print integers - count of strange numbers belonging to the interval .

Constraints

Sample Input

5
7 25
45 50
1 100
99 103
0 1000000

Sample Output

10
1
26
0
96

Explanation
First testcase: There are strange numbers that belong to the interval . They are .
Second testcase: Only satisfies the given constraints.